백준 | IF문 좀 대신 써줘

백준 IF문 좀 대신 써줘

아래 코드를 제출하면 시간 초과로 오답 처리된다..
n과 m의 최댓값이 100,000이고, 2중 for 문이 사용되었기 때문이다.
(최악의 경우 10,000,000,000번의 연산이 필요하기에 제한된 시간 1초로 부족하다.)

# 오답(시간 초과)


import sys

n, m = map(int, sys.stdin.readline().split())

mapping = []
for _ in range(n):
    name, value = sys.stdin.readline().split()
    mapping.append((name, int(value)))

for i in range(m):
    value = int(sys.stdin.readline())

    for j in range(n):
        if value <= mapping[j][1]:
            print(mapping[j][0])
            break

주어진 값의 칭호를 구할 때 이진 탐색을 활용하면, O(n)의 시간 복잡도를 O(log n)으로 줄일 수 있다.
이때, 전체 시간 복잡도는 O(m * log n)이 되므로, 최악의 경우에도 1초 이내로 연산이 끝난다!

# 정답


import sys

n, m = map(int, sys.stdin.readline().split())

mapping = []
for _ in range(n):
    name, value = sys.stdin.readline().split()
    mapping.append((name, int(value)))

for _ in range(m):
    value = int(sys.stdin.readline())

    left = 0
    right = n - 1
    result = 0
    
    while left <= right:
        mid = (left + right) // 2

        if value <= mapping[mid][1]:
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    
    print(mapping[result][0])