[백준/Python] 1620번 나는야 포켓몬 마스터 이다솜 문제

■ 1620번 나는야 포켓몬 마스터 이다솜 문제

 

출처: 백준 1620번 나는야 포켓몬 마스터 이다솜 문제

 

■ 코드 풀이

 

포켓몬에는 이름과 번호가 있으므로, 딕셔너리 자료유형을 사용해야 한다는 것은 어렵지 않게 추측할 수 있습니다. 그래서 포켓몬 번호가 key이고 이름이 value인 pokenmon_dict를 선언했습니다.

최종 정답을 출력할 때는 try & except 구문을 활용했습니다. 우선 정답 target을 int로 변환해 보고, 성공하면 입력받은 값은 숫자이므로 그대로 key값을 활용하여 이름을 출력합니다.

입력받은 값이 이름이면 int로 변환 시, 'ValueError'가 나오게 됩니다. 이 경우에는 value 값을 이용하여 key값, 이름을 출력하도록 코드를 작성했습니다. 그게 아래의 최초 코드입니다.

 

그러나 아래 코드는 시간초과가 발생했습니다. 이유를  생각해 보니, value 값으로 key 값을 찾으려면 딕셔너리를 한번 쭉 순회해야 합니다. 이 작업이 반복적으로 될 경우, 시간이 오래 걸리게 되겠죠. 그래서 시간초과가 발생한 것으로 추측했습니다. 

# 시간 초과가 발생한 코드
import sys

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

pokemon_dict = dict()
pokemon_num = 1

for _ in range(N):
    pokemon_name = sys.stdin.readline().strip()
    pokemon_dict[pokemon_num] = pokemon_name
    pokemon_num += 1

for _ in range(M):
    target = sys.stdin.readline().strip()
    
    try: # 정수인 경우 이름을 출력 
        target = int(target)
        print(pokemon_dict[target])

    except ValueError: # 이름인 경우 번호를 출력
        for key,value in pokemon_dict.items():
            if value == target:
                print(key)

 

그래서 아래와 같이 코드를 바꿨습니다. 처음 코드와 동일하게 포켓몬 번호를 key, 이름을 value로 하는 딕셔너리를 만들었고 그리고 이를 거꾸로 이름을 key, 번호를 value로 하는 'reverse' 딕셔너리도 만들었습니다.

이렇게 하면 메모리는 2배 차지하지만, 시간은 훨씬 단축할 수 있습니다. 이름을 번호로 출력하는 과정에서 매번 리스트를 순회할 필요가 없이, 바로 reverse 딕셔너리를 활용하면 되니까요.

# 딕셔너리를 순회하는데 너무 많은 시간이 걸린 것으로 추측하여 수정한 코드 (정답 코드)

import sys

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

pokemon_dict = dict()
pokemon_num = 1

for _ in range(N):
    pokemon_name = sys.stdin.readline().strip()
    pokemon_dict[pokemon_num] = pokemon_name
    pokemon_num += 1


pokemon_dict_reverse = {value:key for key, value in pokemon_dict.items()}

for _ in range(M):
    target = sys.stdin.readline().strip()
    
    try: # 정수인 경우 이름을 출력 
        target = int(target)
        print(pokemon_dict[target])

    except ValueError: # 이름인 경우 번호를 출력
        print(pokemon_dict_reverse[target])