1차 시도 때에는 반복문을 중첩으로 사용했었기 때문에 시간 초과가 났었던 문제다.
문제에서의 시간 제한이 1초(추가 시간 없음)이었는데 그냥 무지성 구현으로 풀어버린 나 반성하세요.
import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split()) # N: 칭호의 개수, M: 칭호를 출력해야 하는 캐릭터 개수
tag = [list(input().rstrip().split()) for _ in range(N)]
case = [int(input().rstrip()) for _ in range(M)]
for i in range(M):
for j in range(N):
if case[i] <= int(tag[j][1]):
print(tag[j][0])
break
이분탐색을 통해 시간을 단축시켜줬고,
M
번의 반복을 통해 bisect_left()
함수를 사용해줌으로써 문제를 해결했다.
import sys
from bisect import bisect_left
input = sys.stdin.readline
N, M = map(int, input().rstrip().split()) # N: 칭호의 개수, M: 칭호를 출력해야 하는 캐릭터 개수
tag, power = [], []
for _ in range(N):
a, b = input().rstrip().split()
tag.append(a)
power.append(int(b))
for _ in range(M):
print(tag[bisect_left(power, int(input().rstrip()))])
▶️ 시간복잡도 생각하며 문제 풀기 젭알!!