[파이썬/백준1620] 나는야 포켓몬 마스터 이다솜

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

 

실버 4 문제로 쉬운문제인데 일단 입력받는 N,M의 범위가 100,000까지다.

 

이런 문제는 주로 list에서 for문을 이용해 Brute force 탐색을 하면 시간초과를 보는 경우가 많았다.

 

단순히 겹치는 요소만 찾아내는 것이라면 set를 이용해서 intersection 등을 이용할 수 있겠지만..

 

포켓몬의 이름을 입력했을 때 포켓몬 인덱스를 출력하는 것 말고도

포켓몬 인덱스를 입력했을 때 포켓몬의 이름을 출력하는 코드를 작성해야 하므로 인덱스 접근이 불가능한 set를 이용할 수는 없을것 같았다.

 

따라서 dictionary를 이용하기로 했다.

 

사실 처음엔 딕셔너리를 2개 사용한다는 생각을 못하고, dict{"포켓몬이름" : "인덱스"} 형태로 저장해서 보통의 key값과 value를 이용하여 찾는 방식의 코드를 작성했다. (아쉽게도 코드를 저장하지 않고 지운 뒤에 블로그가 만들어져 실패 코드는 없다.)

 

그런데 시간초과가 뜨길래 구글에서 검색을 해보니 딕셔너리의 KEY와 VALUE를 모두 탐색하는 방식은 시간복잡도에서 딱히 유리한점이 없고, 차라리 두개의 딕셔너리를 만들어서 KEY값까지만 탐색하여 출력하도록 하는 방식을 이용하라는 힌트를 얻을 수 있었다.

 

해당 힌트를 보고 작성한 코드는 아래와 같고, 시간초과 없이 해결할 수 있었다.

import sys

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

Name_dict = {}
Index_dict = {}
Answer = []

for i in range(1, N+1):
    pocketmon_name = sys.stdin.readline().strip()
    Index_dict[pocketmon_name] = i
    Name_dict[i] = pocketmon_name

for j in range(M):
    pocketmon_name = sys.stdin.readline().strip()
    try: # 입력이 숫자면
        int(pocketmon_name)
        Answer.append(Name_dict[int(pocketmon_name)])
    except: # 입력이 이름이면
        Answer.append(Index_dict[pocketmon_name])
# print("----")

for k in range(len(Answer)):
    print(Answer[k])