[알고리즘] 백준 19637 IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

 

이진 탐색 문제다.

 

주어지는 N과 M이 둘 다 10^5 까지의 범위기 때문에, 

if문으로 전부 비교하게 되면 10^10으로 1초의 시간제한을 벗어나게 된다.

 

처음에 문제에 접근할 때는, 이진탐색으로 칭호를 기준으로 이진탐색하면서 ~칭호 이하의 개수만큼 ~칭호를 출력,

그 초과, 다음 이하의 개수만큼 ~칭호를 출력 하려고 생각했는데, 거꾸로 생각하면 더 편한 문제였다.

 

거꾸로 숫자를 주고 그 숫자가 어디 칭호의 범위 내에 들어가는지 이진탐색으로 찾은 뒤, 그 칭호에 맞는 결과를 출력하면 주어진 시간 내에 문제를 해결할 수 있다. 

 

해결코드

import sys

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

title = []
for _ in range(n):
    a, b = sys.stdin.readline().rstrip().split()
    title.append((a, int(b)))

atk = []
for _ in range(m):
    tmp = int(sys.stdin.readline().rstrip())

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

        if tmp > title[mid][1]:
            left = mid+1
        else:
            right = mid-1
        mid = (left+right)//2
    mid = left
    print(title[mid][0])