[백준/자료구조] 1620: 나는야 포켓몬 마스터 이다솜 - 파이썬

문제

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

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

 

시도한 풀이 (시간 초과)

 

리스트를 사용하면 시간 초과가 생길 것 같아 리스트보다 시간복잡도가 유리한 딕셔너리를 이용하였다.

생각과 다르게 시간초과가 발생하였는데 혼자서 고민하여 답을 찾을 수 없어 질문탭에서 확인하였다.

힌트를 찾을 수 있었다. 

"dict를 쓰지 않고 단순히 pair로 list에 저장한 것과 차이가 없는 코드입니다. 입력을 받으면 그걸 키로 직접 대입해서 한 번에 구해보세요." - 출처

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
poke = {}
for i in range(n):
    key = i + 1
    value = input().rstrip()
    poke[key] = value

for i in range(m):
    quest = input().rstrip()
    if quest.isdigit():
        for key, value in poke.items():
            if key == int(quest):
                print(value)
    else:
        for key, value in poke.items():
            if str(value) == str(quest):
                print(int(key))

문제의 코드가 for key, value in poke.items()가 13, 17번 라인에 사용되었다.

{포켓몬 번호 : 이름} 만 딕셔너리에 저장해서 인덱스 탐색을 하여 시간초과가 발생하였다.

 

이를 해결하기 위해 딕셔너리에 {포켓몬 이름 : 번호}, {번호 : 포켓몬 이름} 값을 저장하여 value를 찾지 않고 key 값만 빠르게 찾아서 인덱스 탐색 과정을 생략하고자 하였고 코드 수정을 통해 통과하였다.

 

제출한 풀이 (정답)

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

dict = {}
for i in range(1, n + 1):
    a = input().rstrip()
    dict[i] = a
    dict[a] = i

for i in range(m):
    quest = input().rstrip()
    if quest.isdigit():
        print(dict[int(quest)])
    else:
        print(dict[quest])