[BOJ] 1620. 나는야 포켓몬 마스터 이다솜

Jimeaning·2023년 4월 10일

구현 딕셔너리 해시

코딩테스트

목록 보기

68/143

Python3

문제

입출력

입출력 예시

키워드

구현
해시 자료구조
딕셔너리

주요 포인트

리스트를 사용했더니 시간 초과가 떴다.
리스트는 탐색할 때 시간복잡도가 O(n)이라 index에 따라 탐색할 때 데이터 양에 따라 적합하지 않을 수도 있다.
따라서 자료구조 개선이 필요하다. 파이썬 dictionary는 hash table을 사용해 시간복잡도가 O(1)이다.
이 문제는 sys.stdin.readline()과 딕셔너리를 사용해야 한다.

포켓몬 개수 n과 질문 m개를 입력받는다.
포켓몬이 들어갈 mon 딕셔너리를 선언한다.

반복문 (1부터 n까지)
포켓몬 이름을 입력받는다. 이때 rstrip() 함수를 사용해서 뒤에 적히는 공백을 없앤다.
딕셔너리에 key: value로 번호: 이름, 이름: 번호로 한번씩 저장해준다.

반복문 (0부터 m까지)
질문을 입력받는다

만약 질문(q)가 숫자라면, q 숫자에 해당하는 포켓몬 이름을 출력한다.
문자라면, 이름에 해당하는 포켓몬 번호를 출력한다.

(23.4.13 추가) rstrip로 공백을 제거해주지 않으면 키랑 값 쌍이 안 맞아서 KeyError가 뜬다.
딕셔너리 하나에는 순서와 포켓몬 이름을, 또 하나에는 포켓몬 이름과 순서를 저장해서 만들어 준다. 그러면 순서를 물을 땐 포켓몬 이름을, 반대의 경우는 반대를 출력할 것이다. 딕셔너리는 키 값으로만 value에 접근할 수 있다.

최종 코드

import sys

n, m = map(int, sys.stdin.readline().split())
mon = {}

for i in range(1, n+1):
    a = sys.stdin.readline().rstrip()
    mon[i] = a
    mon[a] = i
    
for i in range(m):
    q = sys.stdin.readline().rstrip()
    
    if q.isdigit() == True:
        print(mon[int(q)])
    else:
        print(mon[q])