[#19637] IF문 좀 대신 써줘

문제

#19639 IF문 좀 대신 써줘
Silver3
적용 알고리즘: 이분 탐색 알고리즘

---

풀이 방법

• 이분 탐색으로 정렬된 것은 칭호(오름차순)이고, 각각의 입력된 전투력을 이분탐색으로 칭호에서 찾는다.

코드 흐름

1. 사용자에게서 입력값을 저장한다.
2. 칭호가 입력된 전투력보다 같거나 높으면 high를 갱신해주고, 낮으면 low를 갱신하고 이를 low와 high가 만날 때까지 반복한다.

코드

def binary_search(status, target):
    low = 0
    high = len(status) - 1
    result = 0
    while(low <= high):
        mid = (low + high) // 2
        if (status[mid][1] >= target):
            high = mid - 1
            result = mid
        elif (status[mid][1] < target):
            low = mid + 1
    print(status[result][0])

n, m = map(int, input().split())

status = []
for i in range(n):
    temp = []
    s, pow = input().split()
    temp.append(s)
    temp.append(int(pow))
    status.append(temp)

power = []
for i in range(m):
    power.append(int(input()))

for i in range(m):
    binary_search(status, power[i])

체감 난이도: 4.5/5
Python3으로 채점하면 시간초과가 나고, PyPy3으로 채점하니 통과가 되었다. 솔히 히 이 문제를 보고 이분탐색으로 풀자! 라는 아이디어는 바로 안떠오를 것 같다… 이 문제로 이분탐색이 훨씬 빠르다는 것을 알게 되었다.