백준 19637 IF문 좀 대신 써줘

🐸 문제 정보

19637번: IF문 좀 대신 써줘

 

🤖 알고리즘

이진탐색

 

⏱️ 풀이 시간

16.22m

 

📝 풀이

이진탐색 문제였다.

칭호의 이름과 상한점을 리스트에 넣은 후,

start는 0부터, end는 n - 1부터 시작해서 이진탐색을 진행하면 된다.

문제에 이미 비내림차순(==오름차순)으로 정렬되어 입력된다고 적혀있기 때문에, 칭호에 대해서 정렬을 하지 않아도 된다. 마찬가지로 end 역시 입력으로 주어지기에 len으로 길이를 구할 필요 없다.

다른 사람들의 풀이를 보면서 왜 전부 정렬을 한 번 더 하는지 모르겠다 느꼈ㄷㅏ...

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
emblem = [list(input().rstrip().split()) for _ in range(n)]

def binary(score):
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2
        if int(emblem[mid][1]) < score:
            start = mid + 1
        else:
            end = mid - 1
    return emblem[start][0]

for _ in range(m):
    print(binary(int(input().rstrip())))