[자료구조/해시] 백준 1620 나는야 포켓몬 마스터 이다솜 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 포켓몬 이름을 순서대로 입력받습니다. 입력받은 순서대로 번호를 부여하며(1,2,3...) 숫자 또는 포켓몬 이름으로 질문합니다. 숫자가 입력으로 들어오면 해당 포켓몬 이름을, 이름이면 번호를 출력해야 합니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 문제 설명이 충격적으로 길었습니다.. 열심히 읽었으나, 결국 앞 내용은 필요 없었습니다. 그저 사전 형식으로 입력받고 출력하시면 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
# 입력
dict = dict()
for i in range(N):
    dict[i+1] = input().rstrip() #포켓몬 번호, 이름

#출력
for i in range(M):
    question = input().rstrip()
    try:
        answer = dict.get(int(question))
        print(answer)
    except: #문자일 경우
        for key, value in dict.items():
            if value == question:
                print(key)

 단순히 dictionary 형식으로 구현하면, value로 key를 탐색하는 시간이 너무 오래 걸렸습니다. (시간 초과)

 

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
# 입력

lst = [] #이름 저장
dict = dict() #번호랑 이름 매칭
for i in range(N):
    lst.append(input().rstrip())
    dict[lst[i]] = i+1 #포켓몬 이름, 번호

#출력
for i in range(M):
    question = input().rstrip()

    # 숫자면 list에서 탐색
    if question.isdigit():
        print(lst[int(question)-1])
    else:
        print(dict[question])

 시간을 줄이려면 메모리를 더 쓰면 되죠. 이름을 따로 저장한다음, 숫자면 리스트에서 탐색했습니다.