[백준] 19637번 IF문 좀 대신 써줘 [Python] - 이진 탐색

 

 

 

주어진 전투력 기준마다 정해진 칭호가 있다.

전투력에 따라 칭호를 출력하는 문제

 

이진 탐색은 그리드 탐색$($처음부터 끝까지 모든 경우를 탐색$)$에 비해 빠르다.

우선 정렬된 경우에 유용하기 때문에, 정렬 되지 않은 자료에 대해서는 정렬이 필요하다.

이번 문제는 비내림차순으로 정렬되어 있는 자료가 주어지기 때문에 딱히 정렬할 필요는 없다.

 

모든 경우의 수가 $N$가지일 때, 이진 탐색은 대략 $log_{2}{N}$가지이다.

 

가장 많은 탐색을 해야하는 경우

100번의 탐색을 7번의 탐색으로

1000번의 탐색을 10번의 탐색으로 마칠 수 있다.

 

문제

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

예를 들어, 전투력 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개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

 

처음에는 dict를 사용해 정보를 저장하고 그리드 탐색으로 진행했더니 시간 초과가 나왔습니다.

그래서 이진 탐색 알고리즘을 작성했고, 이후 bisect 모듈을 사용한 코드도 작성해봤습니다.

import sys
N, M = map(int, sys.stdin.readline().split())

d = {}  # 전투력을 key로 칭호를 value로 dict로 저장
for _ in range(N):
    name, power = sys.stdin.readline().split()
    if int(power) not in d:
        d[int(power)] = name
powers = tuple(d.keys())  # 전투력만 따로 tuple로 저장

# 각 전투력에 맞는 호칭 출력
for _ in range(M):
    # 시작 인덱스: 0, 마지막 인덱스 : 전투력의 개수 - 1
    s, e = 0 , len(powers)-1
    
    # 확인할 전투력
    power = int(sys.stdin.readline())

    # 이진 분류
    while s!=e:
        m = (s+e)//2  # 중간값
        p = powers[m] # p : m+1번 째 전투력

        # 확인할 전투력이 p보다 작거나 같으면
        # 더 작은 전투력이 있는지 확인해야함 -> e = m
        # 아니면 더 높은 전투력에 대해 확인해야함 -> s = m+1
        if power <= p:
            e = m
        else:
            s = m+1
    print(d[powers[s]])

 

시간 초과 나온 풀이

import sys
N, M = map(int, sys.stdin.readline().split())
d = {}
for _ in range(N):
    name, power = sys.stdin.readline().split()
    if int(power) not in d:
        d[int(power)] = name
for _ in range(M):
    power = int(sys.stdin.readline())
    for p, n in d.items():
        if power <= p:
            print(n)
            break

 

bisect: 이진 탐색 알고리즘 모듈
bisect를 사용한 방법 - 위에 것 처럼 dictionary로 풀이 

import sys
import bisect
N, M = map(int, sys.stdin.readline().split())

d = {}
for _ in range(N):
    name, power = sys.stdin.readline().split()
    if int(power) not in d:
        d[int(power)] = name
powers = list(d.keys())

for _ in range(M):
    power = int(sys.stdin.readline())
    
    # bisect_left를 통해 powers에 있는 원소들 중 
    # power가 처음으로 작거나 같은 요소의 인덱스를 구할 수 있음.
    print(d[powers[bisect.bisect_left(powers, power)]])

 

bisect 모듈과 list로 풀이

import sys
import bisect
N, M = map(int, sys.stdin.readline().split())

# 칭호와 전투력 -> 리스트에 저장
names = [0]*N
powers = [0]*N
for i in range(N):
    names[i], power = sys.stdin.readline().split()
    powers[i] = int(power)

# 각 전투력이 속한 인덱스로 칭호 출력
for _ in range(M):
    power = int(sys.stdin.readline())
    print(names[bisect.bisect_left(powers, power)])

 

예제 입력 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