[백준][파이썬] 19637번 IF문 좀 대신 써줘

 19637번 : IF문 좀 대신 써줘

문제

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

예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 

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

입력

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

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

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

출력

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

링크

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

19637번: IF문 좀 대신 써줘

 

 접근 방법

1. 전투력의 칭호와 상한값을 딕셔너리로 저장한다.
2. 입력 받는 값을 가지고 이진 탐색을 통해 전투력의 칭호를 찾는다.
   1. 이때 특정 값을 찾는 것이 아니라 어느 범위 안에 있는지를 판단해야 한다.

이진 탐색 참고 자료 : [알고리즘] Binary Search / 이진 탐색 — y-seo의 딩코 기록들 (tistory.com)

[알고리즘] Binary Search / 이진 탐색

 

풀이

1. 이진 탐색 활용

일반적인 이진 탐색의 코드를 아래와 같이 바꾸어 작성하였다.

def binary_search(array, target, start, end): #이진탐색
    res = 0
    while start <= end:
        mid = (start + end) // 2 
        if array[mid][0] >= target: #범위에 맞는 경우
            end = mid - 1
            res = mid
        else: #범위를 낮추는 경우
            start = mid + 1
    return array[res][1]

만약 target 값이 mid에 해당하는 전투력 상한값보다 큰 경우에는 현재 mid 값에 해당하는 전투력보다 더 높은 전투력을 가지므로 start 값을 증가시켜주어야 한다.

만약 target 값이 mid에 해당하는 전투력 상한값보다 작거나 같은 경우에는 현재 mid 값에 해당하는 전투력을 잠시 저장해두고 (맞을 수도 있으니까) end 값을 감소시켜 범위에 딱 알맞는지 확인한다.

 

 전체코드

import sys

n, m = map(int, sys.stdin.readline().split())

system = {}
for i in range(n): #딕셔너리로 전투력 칭호와 상한값 저장
    name, standard = sys.stdin.readline().split()
    system[i] = int(standard), name

def binary_search(array, target, start, end): #이진탐색
    res = 0
    while start <= end:
        mid = (start + end) // 2 
        if array[mid][0] >= target: #범위에 맞는 경우
            end = mid - 1
            res = mid
        else: #범위를 낮추는 경우
            start = mid + 1
    return array[res][1]

for j in range(m): #전투력 판단
    target = int(sys.stdin.readline())
    result = binary_search(system, target, 0, n-1)
    print(result)