Baekjoon 1620번 나는야 포켓몬 마스터 이다솜

문제

https://www.acmicpc.net/problem/1620

걸린 시간

01 : 46 : 00

풀이

Python3

import sys
input = sys.stdin.readline

def binsearch(tmp, category):
    left = 0
    right = len(category)-1
    while left <= right:
        mid = (left + right) // 2

        if tmp > category[mid][0]:
            result = category[mid][1]
            left = mid + 1
        elif tmp < category[mid][0]:
            result = category[mid][1]
            right = mid - 1
        else:
            result = category[mid][1]
            break

    return result

if __name__ == "__main__":
    N, M = map(int, input().split())    

    dic = {chr(i):(i-0x41) for i in range(0x41, 0x5a+1)}

    word = [[] for _ in range(0, 26)]
    num = []

    for i in range(0, N):
        tmp = input().strip()
        word[dic.get(tmp[0], '-1')].append([tmp, i+1])
        num.append([tmp, i+1])

    for i in range(0, 26):
        word[i].sort()

    result = [] 

    for i in range(0, M):
        tmp = input().strip()
        if dic.get(tmp[0], -1) != -1:
            category = word[int(dic.get(tmp[0], -1))]
            result.append(binsearch(tmp, category))
        else:
            result.append(num[int(tmp)-1][0])

    for i in result:
        print(i)

도감에 수록되어 있는 포켓몬 이름의 첫글자가 영어 대문자인걸로 보아, 시작하는 알파벳 순으로 분류하라는 힌트임을 알 수 있다. word

포켓몬의 이름을 입력받아 포켓몬의 번호를 찾기 위해서는 번호를 기준으로 정렬된 목록이 필요하다. num

이분 탐색은 문자열 검색에도 사용할 수 있다.