[구현] (2-3) combinations의 시간복잡도

문제:  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

 

 

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

N, K = map(int, input().split())
num_list = list(map(int, input().split()))
comb_list = list(combinations(num_list, 3)) #O(100^3/3) ~= 180,000
sum_list = []
for comb in comb_list:
    sum_list.append(sum(comb)) #O(180,000)
sum_set_list = sorted(set(sum_list), reverse=True)
# set<- O(180,000)
#sort <- O(18e4ln180000) = 180,000 * ln(2^10 * 180) = 180,000 * ln(2^10 * 2^8)
# = 18 * 180,000
print(sum_set_list[K-1])

N의 최대 100이기 때문에, 100개 중 세개를 택하는 조합을 계산하는 수 = 100C3 = 1,000,000 / 6 ~= 180,000 ( O(N^3) )

그다음 각 comb들 더하기: 180,000 ( O(N^3) )

set으로 만들어서 중복값 제거하기: 180,000 (O(N^3))   #본래 list -> set으로 바꾸는것은 O(N)이므로

sort하기  18 * 180,000   (N^3 ln (N^3) )

즉 전체 계산 = 21 * 18e4  ~= 20*20e4 = 4e6 <= 2억 (가능)!

Big-O complexity = O(N3)+O(N3)+O(N3)+O(N3logN3)≈O(N3logN)