[파이썬 알고리즘 문제풀이 입문] 코드 구현력 기르기 - K번째 큰 수

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

문제

1~100 자연수가 적힌 N장의 카드를 갖고 있습니다. (같은 숫자의 카드가 여러 장 있을 수 있다.) 이 중에서 3장을 뽑아 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우의 수를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.

 

 

풀이

• 내 풀이

from itertools import combinations
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
cards = list(map(int, input().split()))
cards.sort(reverse = True)

three = list(combinations(cards, 3))
result = set()

for i in range(len(three)):
    result.add(sum(three[i]))
    if i == (K-1):
        result = list(result)
        print(result[i])
        break

 

• 답안

N, K = map(int, input().split())
a = list(map(int, input().split()))
res = set()  #중복을 제거한다.

# 3중 for문
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])

- 처음에 문제를 풀 때 '조합'과 관련된 내용이라고 생각하고 combinations를 사용해서 문제를 풀었다.

- 답안을 보니, 뽑은 3장의 카드의 합이 중복될 수도 있다는 점을 놓쳤다는 것을 깨달았다. 이런 경우 set()을 활용해주면 된다는 힌트를 얻고 다시 문제를 풀어보았다.

- list()에서는 값을 추가할 때 .append()로 추가해줬다면, set()에 값을 추가할 때에는 .add()로 추가해줘야 한다.

- set()은 sort()가 불가능하고, 인덱스로 접근하는 것도 불가능하기 때문에 list()로 바꿔서 접근해야 한다.

- 나는 처음에 내림차순으로 먼저 정렬을 해준 뒤에 3장씩 뽑고 합을 구했는데, 답안에서는 먼저 3장씩 뽑고 합을 구한 이후에 내림차순으로 정렬을 진행해주었다.

- 3중 for문을 피하고 싶어서 조합을 사용해보았다.