백준 1620 - 파이썬

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

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

 

문제 풀이

문제가 길어서 처음에 뭐지 싶었는데 포켓몬 얘기는 중요한 부분이 아니기 때문에 예제 입출력 조건만 잘 읽어보면 이해할 수 있는 문제였다. n개의 포켓몬 이름이 있을 때 이에 대한 m개의 질문과 일치하는 값을 출력하면 되는 문제였고, 바로 코드 작성을 시작했다. 금방 풀 수 있을 줄 알았는데 계속 시간초과가 나서 답답했다. 시간 초과가 난 코드는 다음과 같다.

 

import sys, re
input = sys.stdin.readline

n,m = map(int,input().split())

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

questions = dict()
for i in range(1,m+1):
    questions[i] = input().rstrip()

for i in range(1,m+1):
    nums = re.findall(r'\d+', questions[i])
    if nums:
        print(nickNames[int(nums[0])])
    else:
        for k,v in nickNames.items():
            if v == questions[i]:
                print(k)

# for i in range(1,m+1):
#     if questions[i].isdigit():
#         print(nickNames[int(questions[i])])
#     else:
#         for k,v in nickNames.items():
#             if v == questions[i]:
#                 print(k)

 

isdigit() 함수를 이용하여 문자와 숫자를 구별하면 통과될까 싶어 주석처리 된 부분도 실행해 봤지만 역시나 시간 초과가 났다. 다른 방법이 있을까 싶어 30분 동안 더 고민해 봤지만 딱히 다른 방법이 떠오르지 않아 다른 사람들의 코드를 참고해 봤다.

 

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])

 

나의 풀이와 전체적인 틀은 같지만 차이점이 존재했다. 나의 경우는 포켓몬 이름이 저장될 딕셔너리와 질문들을 저장할 딕셔너리를 따로 구분하고 둘의 key와 value를 맞췄다. 하지만 위의 코드에서는 입력된 문자열과 숫자를 모두 저장함으로써 탐색 시 반복문의 개수를 줄였다.

리스트의 경우 반복문의 시간복잡도가 O(n)이기 때문에 n의 개수가 늘어날수록 시간이 더 오래 걸리지만 딕셔너리의 경우 O(1)이기 때문에 모든 경우의 수를 저장해서 탐색해도 시간이 더 걸릴 일이 없는 것이다.

 

이처럼 하나의 딕셔너리에 문자열과 숫자를 모두 저장하는 방법도 있지만, 문자열을 저장할 딕셔너리와 숫자를 저장할 딕셔너리를 각각 만들어 주는 방법도 있다. 아래 코드는 해당 블로그를 참고했다.

 

import sys

n, m = map(int, input().split())

dict_int = {}
dict_name = {}
for i in range(1, n+1):
    name = sys.stdin.readline().strip()
    dict_int[i] = name
    dict_name[name] = i

for _ in range(m):
    item = sys.stdin.readline().strip()
    if item.isdigit() == True:  # isdigit -> O(n)
        print(dict_int[int(item)])
    else:
        print(dict_name[item])

 

느낀점

이번 문제는 key와 value의 값을 두 개의 딕셔너리가 모두 일치해야 된다는 틀에 갇혀있었기 때문에 풀지 못했다. 딕셔너리의 key와 value특성만 이해하면 되지 꼭 둘을 일치시킬 필요가 없었는데 말이다. 사고의 유연함을 가지는 게 조금이라도 의식적이지 못하다면 쉽게 틀에 갇히게 되는 것 같다. 이번 문제를 풀면서 다시 한번 상기시켰으니 앞으로 문제를 풀 때도 사고의 틀에 갇히지 않도록 노력해야 되겠다.