Algorithm - K번째 큰 수

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[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번째 수는 반드시 존재한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_3.txt', 'rt')

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])


# 출력 : 143

 

input_3.txt(입력)

10 3
13 15 34 23 45 65 33 11 26 42

 

 

중요내용

1. 3중 for문은 총 n개의 숫자 중에서, 중복을 허용하지 않고 3개의 숫자를 모두 뽑는 코드이다.
2. 변수 res는 집합(set) 자료형이기 때문에, 중복을 허용하지 않는다.
3. 집합(set) 자료형에 데이터를 추가할 경우에는 add() 함수를 사용해야 한다.(append() 함수 사용x)
4. 집합 자료형은 순서가 없기 때문에, sort() 함수를 사용해서 정렬을 할 수 없다.
5. 해당 집합 자료형의 데이터를 정렬시키기 위해서는 반드시 집합 자료형을 리스트 자료형으로 형 변환한 후에, sort() 함수를 사용해서 정렬을 해야한다.
6. sort(reverse=True) 코드는 특정 자료형의 데이터를 내림차순(큰 수부터 작은 수로)으로 정렬하는 것을 의미한다.