유형정리(이분탐색) - 백준 19637

19637번: IF문 좀 대신 써줘 (acmicpc.net)

19637번: IF문 좀 대신 써줘

 

문제

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

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

if power <= 10000
 print WEAK
else if power <= 100000
 print NORMAL
else if power <= 1000000
 print STRONG

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

입력

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

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

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

출력

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

예제 입력 1 복사

3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000

예제 출력 1 복사

WEAK
WEAK
WEAK
NORMAL
NORMAL
NORMAL
STRONG
STRONG

예제 입력 2 복사

3 5
B 100
A 100
C 1000
99
100
101
500
1000

예제 출력 2 복사

B
B
C
C
C

 

이 문제는 처음 볼 때 대체 IF문을 적어서 만들어라는 건지, 이분탐색이랑 무슨 상관이 있는건지 정말 1도 이해가 안되어서 한참을 보다가 결국 구글링을 택했다. 구글을 보니, IF문 자체를 적지 않고 리스트나 딕셔너리 형태를 만들어서 해당하는 숫자들이 그 사이로 들어가도록 일종의 IF문을 구현하는 문제였다. 이왕 구글링을 한 김에 좀 더 신박한 풀이가 있어 이분탐색이 아닌 bisect를 사용하여 문제를 해결해보았다.

 

※ bisect란?

- 이분탐색을 쉽게 사용하도록 구현해놓은 python 모듈.

ex)

a = [1,3,5,6,7]

b = 5

일 경우, bisect(a,b) = 3 이 된다. index를 반환하는 것으로 기본을 오른쪽으로 선택한다. 5는 3,5 부분과 5,6 부분이 선택될 수 있는데 여기서 bisect(a,b)는 5,6 부분이 선택되어 index = 3의 위치에 들어가게 된다.

여기서 왼쪽을 선택하고 싶다면 bisect_left(a,b)로 구현해주면 index = 2의 위치인 3,5 부분을 선택하게 된다.

 

※ 알고리즘

1. n과 m을 입력받는다.

2. 칭호 갯수와 캐릭터들의 갯수를 입력받을 빈 리스트를 만든다.

3. 칭호와 캐릭터 갯수를 모두 n개 만큼 반복하면서 입력받고, 빈 리스트에 담는다. (이 때, 숫자 비교를 위해 캐릭터 갯수는 int형으로 강제형 변환 시켜준다.)

4. 반복적으로 비교할 숫자를 bs로 입력받고 bisect_left로 해당 리스트에서 칭호 부분을 선택하도록 만든다.

 

import bisect
import sys

input = sys.stdin.readline

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

name_num = []
char_num = []

for i in range(n):
    name, char = map(str, input().split())
    name_num.append(name)
    char_num.append(int(char))

for i in range(m):
    bs = int(input())
    answer = bisect.bisect_left(char_num, bs)
    print(name_num[answer])

 

조금 신박한 방식으로 풀어보았다. 구글링을 통해서 bisect라는 새로운 방식을 알게 되어 이 방식을 주기적으로 사용해 보려 한다.