[Python] 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

---

문제 풀이

문제 해결 아이디어

3개씩 더하는 조합을 만들어서 리스트에 넣고 sort

조합을 어떻게 만들지 → 조합 쓰면 되지 않을까

• 조합: 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것
  • {’A’, ‘B’, ‘C’}에서 순서를 고려하지 않고 두 개를 뽑는 경우: ‘AB’, ‘AC’, ‘BC’

  # 출처.이코테2021
  
  from itertools import combinations
  
  data = ['A', 'B', 'C'] #데이터 준비
  
  result = list(combinations(data, 2)) #2개를 뽑는 모든 조합 구하기
  print(result)
  
  #[('A', 'B'), ('A', 'C'), ('B', 'C')]
  

1차 시도

from itertools import combinations

# 입력 N(데이터의 수), K(큰 수 차례)
N, K = map(int, input().split())
data = list(map(int, input().split()))
result = []

# 3개의 조합 구하기 + sum 처리 해서 리스트에 넣기
case = list(combinations(data, 3))  # 3개를 뽑는 모든 조합 구하기
for tmp in case:     # 각 조합의 합을 result에 저장
    result.append(sum(tmp))

result.sort(reverse=True)   # 큰 수부터 정렬

print(result[K-1])

 

문제점 / 개선점

pycharm에서는 실행이 안 되는데 코드 문제는 아닌 것 같다 (강의에 올라온 코드도 안 된다)

순열을 쓰는지 조합을 쓰는지 헷갈렸는데 둘의 차이를 잘 익혀두자

---

참고할 코드

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]

학습 내용

for문으로도 가능하다 -> 근데 삼중for문이라 차라리 라이브러리 쓰는 게 더 나은 것 같다
sort(reverse=True)하면 큰 수부터 정렬이 가능하다