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개의 카드값이 입력
된다.10 3
13 15 34 23 45 65 33 11 26 42
출력
첫 줄에 K번째 수를 출력합니다. K번째 수는 반드시 존재합니다.
143
문제 풀이 핵심 point 🔍
point 1. 조합
처음에 인덱스 범위를 생각 안하고 삼중 for문으로 돌리면 되겠지 생각했는데, 예시보다 더 많은 수가 나왔다. 뭐가 문제인지 모르겠어서 문제를 다시 읽어보니 고등학교 때 자주 보던 카드뽑기 문제 ㅎㅎㅎ
이 문제는 조합의 개념을 알아야 풀 수 있는 문제다. 조합은 순열과는 다르게 카드를 뽑는 순서는 상관 없지만, 한번 뽑은 카드를 또 뽑을 수 없다. 이전에 0번 인덱스 부터 삼중 for문으로 돌렸을 때 한번 뽑은 카드를 또 뽑게되니깐 예시보다 더 많은 결과가 나온 것 같다.
# 조합
for i in range(N): # i는 n개 만큼 탐색
for j in range(i+1,N): #j는 i번째에서 선택한 값 다음값을 선택
for k in range(j+1,N): #k는 j번째에서 선택한 값 다음값을 선택
s = num[i]+num[j]+num[k]👉 각 카드는 한 장 밖에 없다.
👉 i번째 카드를 한번 뽑았으니 다음으로는 i+1(j)번째 카드를 뽑고, 그 다음으로는 i+2(k)번째 카드를 뽑아야 한다.
point 2. 중복 제거
1번째 방법: if x not in list:
중복을 제거하는 것 또한 중요하다. 나는 if절에 not in을 이용해서
중복된 값이 없을 시에 리스트에 추가하는 방법으로 풀었다. (아래 풀이1 방법)
2번째 방법: set
set을 이용해서 중복을 제거하는 방법이 있었다. (아래 풀이 2 방법)
문제를 풀기 위해서는 set의 개념과 특징 2가지를 짚고 넘어갈 필요가 있다.
⭐ set 개념
집합(set)은 파이썬 2.3부터 지원하기 시작한 자료형,집합에 관련된 것을 쉽게 처리하기 위해 만든 자료형.
⭐ set의 가장 큰 특징 2가지
1. 중복을 허용하지 않는다. -> 중복 제거 가능
2. 순서가 없다(Unordered). -> 역순 정렬을 위해 나중에 리스트로 다시 변환해줘야 한다.
👉 리스트와 튜플은 순서가 있으므로 인덱싱으로 접근이 가능하지만
set은 순서가 없으므로 인덱싱으로 접근이 불가능하다. 딕셔너리 역시 순서가 없는 자료형이라 인덱싱을 지원하지 않는다.
자세한 건 나중에 포스팅 할 예정이다. 문제 풀기 위해서는 2가지 특징만 잘 알고 있으면 된다.
코드 💻
풀이1 - if s not in ... 이용한 중복제거
# 내 풀이
N, K = map(int, input().split())
num = list(map(int, input().split()))
sum = []
# 조합
for i in range(N): # i는 n개 만큼 탐색
for j in range(i+1,N): #j는 i번째에서 선택한 값 다음값을 선택
for k in range(j+1,N): #k는 j번째에서 선택한 값 다음값을 선택
s = num[i]+num[j]+num[k]
if s not in sum:
# 중복을 제거하면 sum에 입력
sum.append(s)
sum.sort(reverse=True)
# print(sum)
print(sum[K-1])
풀이2 - set을 이용한 중복 제거
N, K = map(int, input().split())
num = list(map(int, input().split()))
sum = []
# 조합
for i in range(N):
for j in range(i+1,N):
for k in range(j+1,N):
s = num[i]+num[j]+num[k]
sum.append(s)
# set으로 중복제거 먼저한 후 - set 특징 1 : 중복을 허용 하지 않음
# 역순 정렬을 위해 list로 다시 변환 - set특징2 : 순서가 없다.
sum = list(set(sum)) # list특징2 : 순서 존재
sum.sort(reverse=True)
# print(sum)
print(sum[K-1])
출처 : 한국정보올림피아드
