[Algorithm] 기초 문제 / K번째 큰 수

▶ 문제

현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려 고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력 하는 프로그램을 작성하세요. 만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값 은 22입니다.

 

▶ 입력 설명

첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력 된다.

 

▶ 출력 설명

첫 줄에 K번째 수를 출력합니다. K번째 수는 반드시 존재합니다.

 

▶ 입력

10 3

13 15 34 23 45 65 33 11 26 42

 

▶ 출력

143

 

---

▷ 내가 짜본 코드

import sys
sys.stdin = open('input.txt', 'rt')
n, k = map(int, input().split())
a = list(map(int, input().split()))

b = []
for i in range(n):
    for j in range(i+1, n):
        for s in range(j+1, n):
            b.append(a[i]+a[j]+a[s])
b = set(b)
b = list(b)
b.sort(reverse=True)
print(b[k-1])

일단은 삼중 for 문을 사용해 세 개 카드 값을 뽑아 더했다.

더한 값을 집어 넣은 배열 b를 만든 후, 중복된 값을 제거하기 위해 set으로 변환하고, 내림차순을 하기 위해 다시 배열로 변환하였다. 

조금 번거롭긴 했어도 결과가 제대로 나와서 안심했다.

 

 

 

▷ 예시 코드

import sys
sys.stdin=open("input.txt", "r")
n, k=map(int, input().split())
a=list(map(int, input().split()))

res=set()
for i in range(n):
    for j in range(i+1, n):
        for m in range(j+1, n):
            res.add(a[i]+a[j]+a[m])
res=list(res)
res.sort(reverse=True)
print(res[k-1])

애초에 값을 담는 테이터 타입을 set으로 생성하면 훨씬 더 간단하게 코드가 짜진다.

나도 이 생각을 안 해 본 건 아닌데, set을 다루는 게 익숙하지 않아서 시도하지 않았던 것 같다.

숙지하고 있다가 나중에 다시 한 번 풀어봐야 겠다. 

 

※ 기억하자 ! set에 값을 집어넣을 때는 add 함수 사용!