K번째 큰 수

it 취업을 위한 알고리즘 문제 풀이

문제

코드

import sys
sys.stdin = open("input.txt","rt")
n,k = map(int,input().split())
card = 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(card[i]+card[j]+card[m])


res = list(res)
res.sort(reverse = True)
print(res[k-1])

문제해결방법

• 카드 3장을 뽑아 구할수 있는 모든 합을 구하고 중복을 제거한 형태의 K번째 큰 수를 구해야 하므로 set 자료구조를 사용했다.
• 3중 for문으로 i를 고정하고 j를 i+1부터 고정한채 m을 j+1부터 n-1까지 고르면서 합을 구하고 다시 j를 증가시키고 다음 합들을 구하고를 반복하여 합을 구한다.
• 선택하는 방법을 다시 구체적으로 나타낸 그림은 아래에 있다.
• 아래와 같이 10개의 숫자가 리스트에 저장되어 있을 때 3숫자를 선택하는 방법은 나열한 방법중 이부를 나타낸 것이다.
• 0번 인덱스(13)를 선택하고 1번 인덱스(15)를 선택한 상태에서
  • 2번 인덱스를 선택, 다시 3번인덱스 선택, 4번인덱스 선택 ...9번인덱스 선택
• 다시 0번 인덱스(13)를 선택하고 2번 인덱스(34)를 선택한 상태에서 
  • 3번 인덱스를 선택, 다시 4번 인덱스를 선택, 5번 인덱스를 선택 .. 9번 인덱스를 선택하면 된다.

 

0	1	2	3	4	5	6	7	8	9
13	15	34	23	45	65	33	11	26	42