K번째 큰 수

1~100사이의 자연수가 적힌 N장의 카드 (같은 숫자 있을 수 있음) 중에서 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록. 기록한 값들 중 K번째로 큰 수를 출력하는 프로그램 (기록한 값들 중에서 같은 값들은 하나로 취급됨)

 

입력예시)

10 3

13 15 34 23 45 65 33 11 26 42

 

*첫번째 줄은 N과 K

두번째 줄은 N개의 숫자가 적힌 카드 

 

출력예시)

143

---

내가 쓴 코드

N, K = map(int,input().split())
lst = list(map(int,input().split()))

sumPreparation = []
sumResults = []
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1, N):
            sumPreparation.append(lst[i])
            sumPreparation.append(lst[j])
            sumPreparation.append(lst[k])

            sumResults.append(sum(sumPreparation))
            sumPreparation.clear()

sumResults = set(sumResults)
sumResults = list(sumResults)

sumResults.sort(reverse=True)
print(sumResults[K-1])

모범답안

n, k = map(int, input().split())
a = list(map(int, input().split()))

res = set()
#빈 set 만들기: 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])

모범답안 보고 반성해보기

일단 칭찬할점: 3가지 뽑는 모든 경우의 수를 구하는 방법 (즉, 조합)을 모범답안과 정확히 똑같이 해냄

ㅋ 근데 이것도 못하면 ㄹㅇ 전과해야하는거 아니냐고

심지어 머리쓰는데 시간과 노력이 좀 걸린걸 보면 확실히 재능있다고 믿거나 그런 오만한 태도를

취해서는 안될듯 그래도 아주아주 오랜만에 알고리즘문제 푸는거니까 봐줘야함

 

근데!!

일단 sumPreparation 리스트는 안만들었어야함

sumPreparation 리스트에 세개씩 넣고 합한 값을 다시 sumResults에 넣고 sumPreparation은 리셋하고

이런 비효율적인 과정을 매반복문에서 반복한건 너무 . 바보같았던 생각

처음부터 그냥 세 개를 더한 값을 sumResults에 바로 넣어도 됐음

 

그리고 sumResults를 리스트로 처음에 설정해서 중복제거하려고 set으로 바꿨다가

다시 sort하려고 리스트로 바꾸는것보다

sumResults를 처음에 set으로 설정해서 (sumResults= set()) 중복 제거하고

리스트로 바꾸면 더 좋았을 것.. 

이러면 구조 변경을 한번만 하니까!!

 

**sumResults를 처음에 리스트로 설정해서 sort하고 set으로 바꾸는건?

안됨: 왜냐면 마지막에 어쨌든 K번째 수를 인덱스K-1를 이용해서 접근해야 하는데

set은 순서가 없는 중복이 불가능한 자료형이기때문.. 결국에는 리스트형태로 있어야 한다!

---

반성했으면 다시 써보기

N, K = map(int, input().split())
lst = list(map(int, input().split()))

sumResults = set()

for i in range(N):
    for j in range(i+1, N):
        for m in range(j+1, N):
            sumResults.add(lst[i]+lst[j]+lst[m])

sumResults = list(sumResults)
sumResults.sort(reverse=True)
print(sumResults[K-1])