문제
문제 해설
칭호의 개수와 캐릭터의 개수가 둘 다 100,000 이므로, Nlog(M) or Mlog(N)안에 끝내는 코드를 짜야합니다.
그래서 칭호를 기준으로 혹은 캐릭터를 기준으로 이분탐색을 진행하면 됩니다.
문제에서 칭호는 비내림차순으로 이미 정렬이 되어 있기 때문에 캐릭터를 하나씩 받아 칭호리스트를 이분 탐색하는 방향으로 진행했습니다.
bisect 라이브러리의 bisect_left는 동일한 value가 존재하면 가장 왼쪽의 인덱스를 반환합니다. 만약 찾고자하는 값이 없다면 사이 값의 오른쪽을 반환하기 때문에 음수 값을 미리 하나 넣어놓고 시작하면 편합니다.
풀이 코드
import sys
import bisect
input = sys.stdin.readline
n, m = map(int, input().split())
title = []
power = [-1]
for i in range(n):
t, p = map(str, input().rstrip().split())
title.append(t)
power.append(int(p))
for _ in range(m):
p = int(input())
index = bisect.bisect_left(power, p)
print(title[index - 1])
