[백준] 콘서트(python)

백준, 콘서트

16466번: 콘서트

TL;DR

• 이진 탐색(Binary search)

문제 요약

1. 1차 티켓팅에서 팔린 티켓의 정보가 주어진다.
2. 2차 티켓팅 때 1차 티켓팅에서 팔리지 않은 티켓 중 살 수 있는 가장 작은 번호의 티켓을 출력한다.

 

- 1차 티켓에 팔린 티켓 정보를 활용하여 2차 때 구할 수 있는 티켓 번호 중 가장 작은 번호를 찾아 추력하면 된다.

- 티켓의 수와 번호의 수가 매우 크기 때문에 완전 탐색으로 풀 경우 시간 초과가 발생한다. 다른 방법을 찾아야 한다.

입출력 형태

입출력 예시

풀이

import sys, bisect

N = int(sys.stdin.readline())
tickets = list(map(int, sys.stdin.readline().split()))
tickets.sort()
max_tickets = tickets[-1]

for i in range(1, max_tickets + 1):
    index = bisect.bisect_left(tickets, i)

    if index < len(tickets) and tickets[index] != i:
        print(i)
        break

    if index == len(tickets) - 1:
        print(max_tickets + 1)

 

완전 탐색으로 원하는 수를 찾을 수 없다면 다음으로 시도해볼 수 있는 방법은 binary search이다.

티켓의 수를 입력 받은 후 입력된 티켓 번호를 작은 순서대로 정렬한다.

1부터 입력 받은 티켓 중 가장 큰 티켓의 번호를 순회하며 이진 탐색을 진행한다.

만약, 숫자가 tickets에 존재하지 않는다면 해당 티켓이 1차 때 팔리지 않은 가장 작은 티켓이므로 출력하고 종료한다.

끝까지 조회했는데도 가장 작은 티켓 번호를 찾을 수 없다면 살 수 있는 티켓의 번호는 1차 때 팔린 티켓의 바로 다음 번호이므로 이를 출력한다.