[백준, Hash] 1620_나는야 포켓몬 마스터

문제 링크 : https://www.acmicpc.net/problem/1620

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

 

처음 이 문제를 봤었을 때, 많이 당황했었다... 살면서 본 코테 문제 중 가장 당황했던 문제였다 ㅎㅎ...

대화하는 부분에서 문제를 푸는데 참고해야하는 중요한 내용이 나오지 않을까해서 다 읽어봤지만 시간낭비였다 ㅋㅋㅋ

 

아무튼

1. 포켓몬 이름

2. 포켓몬의 index (입력된 순서)

 

위 2가지를 동시에 기억하고 있다가, 호출이 되면 return 하는 문제였다.

 

처음에는, hash 함수를 사용해 Key - Value 형태를 Hash 거친 Key - (index, 포켓몬 이름) 이런 식으로 dict에 저장할까 생각했다.

그러나, 위와 같이 저장하면 dict의 value들을 전부 탐색해 포켓몬의 이름과 index를 찾아야하기 떄문에 시간 복잡도가 O(N ^ 2) 로 시간초과가 날 것 같았다.

 

N과 M, 즉, 포켓몬 수와 문제 수가 각각 최대 100,000개로 O(N ^ 2) 가 될시 시간초과가 나는 게 뻔했다.

어쩔 수 없이 dict의 in 함수를 사용해 O(1) 시간복잡도초 찾는 게 해답인 것 같았다.

포켓몬 이름에 대한 딕셔너리와 index 에 대한 딕셔너리 2개를 만드는 방법 외에 1개로 해결할 수 있는 방법이 없나 생각해봤지만 못 찾았다.

 

코드는 이와 같다.

 

import sys

input = sys.stdin.readline

name_dict = {}
index_dict = {}

N, M = map(int, input().split())

for i in range(1,N+1):
    temp = input().split()[0]
    name_dict[temp] = i
    index_dict[i] = temp

for _ in range(M):
    tr = input().split()[0]
    if tr.isalpha(): # 문자열이 문자열이면, 문자열이 숫자이면은 .isdigit
        print(name_dict[tr])
    else: # 숫자인 경우
        print(index_dict[int(tr)])
        # tr이 str 자료형이니 int로 바꿔서 사용

 

다만, 분명 쉬운 코드고 복잡한 알고리즘이 없지만 에러가 계속해서 발생해 힘들었다.

에러 원인은 .split()을 하면 list 형태안에 str 자료형으로 저장된다.

 

기존에는 temp와 tr을 input().split() 이렇게만 저장했다.

이로 인해 마지막 index_dict[int(tr)] 에서 tr의 자료형이 str 이라 생각하고 int를 씌웠지만 자료형이 달라 에러가 발생하는 것이였다.

 

따라서, 값을 읽을 떄, 확실하게 list[0]으로 설정해 list 자료형이 아니도록 구현해서 완성시켰다.