[Silver III] IF문 좀 대신 써줘 - 19637

문제 링크

성능 요약

메모리: 49444 KB, 시간: 408 ms

분류

이분 탐색

문제 설명

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

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

---

풀이

아이디어

최적화문제를 결정문제로 바꾸는것을 정하는것이 가장 중요하다고 판단.
맨 처음에는 이걸 이분탐색으로 왜 풀지? 라는 생각을 했었는데, 입력한 값이 정말 너무너무 커질수가 있어서 납득..


이분탐색으로 탐색할 부분은 칭호 리스트 lst의 인덱스이며, 해당 인덱스보다 큰지 작은지 판단하여 start와 end의 적절한 값을 판단하여 범위를 좁혀줌


또한 데이터 저장방식을 맨 처음에는 딕셔너리로 하려고 했었으나, 차라리 2차원 리스트를 사용하는게 구현이 더 간단해 일부 갈아엎어서 AL을 받았다.

코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
lst = []

def bi_search(target):
    start, end = 0, n
    while start <= end:
        mid = (start + end) // 2
        if target > lst[mid][1]:
            start = mid + 1
        else:
            end = mid - 1  

    return(lst[start][0])

for i in range(n):
    a, b = input().split()
    lst.append([a, int(b)])

for j in range(m):
   print(bi_search(int(input())))

---

회고

이때까지 푼 문제는 단순히 이분탐색이었다면, 결정문제가 무엇인지에 대해 다시 한 번 생각해 볼 수 있던 문제였다. 이분탐색이 단순히 탐색에만 쓰는게 아니라 최적화와 같이 어떠한 문제의 속도를 올리는데 사용할 수 있는 응용에 대해 배웠다.