백준 16466 - 콘서트 (파이썬)

https://www.acmicpc.net/problem/16466

풀이

주어진 티켓 번호 배열에서 가장 작은 사용되지 않은 티켓번호를 찾는 문제이다.

머너저 주어진 티켓 번호 리스트 A를 오름차순으로 정렬한다.

그리고 티켓번호는 1번 부터 시작해야 하므로, 정렬된 배열에서 (인덱스 + 1)과 다른 값이 존재하는 경우, 그 값이 비어 있는 첫번째 티켓 번호이다.

마지막 까지 비어있는 번호가 없으면 N + 1을 출력한다.

시간 복잡도 분석

정렬 : O(N Log N)

탐색 : O(N)

총 복잡도 : O(N Log N)

코드

# 백준 16466 - 콘서트
# 분류 : 정렬
 
N = int(input())
A = list(map(int, input().split()))
 
A.sort()
found = False
for i in range(N) :
    if A[i] != (i + 1) :
        print(i + 1)
        found = True
        break
 
if not found :
    print(N + 1)