📍 문제
(원문은 영어여서 어색한... 한국어로 번역했어요222 )
영잘알들을 위한 원문
문제
미르코는 자신의 생일을 축하하고자, 친구들을 영화관에 초대하고 싶어합니다.
그의 친구들은 모두 큰 규모의 그룹으로 영화관에 가는 것을 좋아합니다.
그래서 그들은 마르코와 자신(친구 본인)을 제외한 특정 수의 미르코 친구들이 함께 영화관으로 함께 가고 싶다며 마르코에게 요청합니다.
하지만, 미르코는 모두를 초대할 돈이 충분하지 않습니다. 그래서 가능한 최소한의 인원을 초대하려고 합니다.
그는 친구들 각각의 요청을 충족할 수 있는 최소한의 그룹 규모를 결정해야 합니다!
이 그룹은 적어도 한 명 이상의 사람으로 구성되어야 합니다.
미르코가 이 그룹의 규모를 결정하는 데 도움을 주세요.
입력
첫 번째 행에는 친구들의 수를 뜻하는 정수 N이 있으며, 그 범위는 2 ≤ N ≤ 10,000입니다.
다음 N개의 행에는 각각 하나의 정수 Z가 있으며, 1 ≤ Z < N입니다.
이 숫자는 미르코 친구들의 요청을 나타내며,
영화관에 함께 가기를 원하는 최소한의 사람 수를 나타냅니다.
출력
미르코가 영화관에 초대할 수 있는 최소한의 사람 수를 한 줄로 출력해주세요.
📍 아이디어
단순 sorting 문제.
초기에 미르코가 미르코 자신만 초대한다고 가정하고, 초대할 최소한의 사람 수를 세팅한다.
그 후 그룹 내의 사람 수가
1. 친구들의 수보다 작거나 같고
2. 정렬된 초대 요청 리스트에서 (그룹 내의 사람 수) 순서일 때의 요청보다 하나 더 많은 사람을 초대했을 때의 요청이 그룹 내의 사람 수일 때보다 큰 경우
loop를 돈다.
→ 너무 거지 같이 적어서 조금 정리하면!
예를 들어, a가 [1, 2, 2, 3]인 경우,
그룹 내의 사람 수가 1부터 시작하면서 반복문을 돌면서 a[그룹 내의 사람 수 - 1] + 1을 계산하면
ret = 1일 때, a[그룹 내의 사람 수 - 1]은 1이므로 a[그룹 내의 사람 수 - 1] + 1은 2.
ret = 2일 때, a[그룹 내의 사람 수 - 1]은 2이므로 a[그룹 내의 사람 수 - 1] + 1은 3.
ret = 3일 때, a[그룹 내의 사람 수 - 1]은 2이므로 a[그룹 내의 사람 수 - 1] + 1은 3.
ret = 4일 때, a[그룹 내의 사람 수 - 1]은 3이므로 a[그룹 내의 사람 수 - 1] + 1은 4.
즉 정렬된 초대 요청을 기반으로 가능한 한 적은 사람을 초대하는 방법을 찾는 문제!
📍 정답 코드
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
ret = 1
while ret <= n and a[ret - 1] + 1 > ret:
ret = a[ret - 1] + 1
print(ret)