[백준] 19637: IF문 좀 대신 써줘 python 구현 / 이분 탐색(bisect)

문제

게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.

예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.

혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.

입력

첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ $10^5$)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ $10^5$)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ $10^5$)

두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 $10^9$ 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다. 

N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

 

풀이

처음 내가 시도한 코드

• 오름차순으로 정렬하여 for문으로 완전 탐색하였다.

import sys

n, m = map(int, input().split())
chingho = [sys.stdin.readline().split() for _ in range(n)]
chingho.sort(key=lambda x: int(x[1]))  # 오름차순 정렬

chars = [int(sys.stdin.readline().strip()) for _ in range(m)]
for char in chars:
    for string, stat in chingho:
        if char <= int(stat):
            print(string)
            break

 

그러나 이 문제의 핵심은 (1 ≤ N, M ≤ $10^5$) !!

문제 읽을 때 범위와 시간을 체크하는 버릇을 항상 들여야 함... 아니면 이렇게 된다 ^_ㅠ

입력을 받는 것도 input() 보다는 sys.stdin.readline()를 쓰자 ! 나는 while True: input()을 대학교 과제부터 자주 썼는데 그냥 한 번 써봤는데 입력에서만 엄~청 오랜 시간이 걸린다.

그런 의미에서 해당 문제는 이분탐색(bisect)으로 풀어야 한다.

 

풀이

import sys

n, m = map(int, input().split())
chingho = [sys.stdin.readline().split() for _ in range(n)]
chingho.sort(key=lambda x: int(x[1]))  # 오름차순 정렬

chars = [int(sys.stdin.readline().strip()) for _ in range(m)]

for char in chars:
    right = len(chingho)
    left = 0
    result = 0
    while left <= right:
        mid = (left+right)//2
        if int(chingho[mid][1]) >= char:
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    print(chingho[result][0])