[파이썬] 백준 15652 : 나는야 포켓몬 마스터

[파이썬] 백준 15652 : 나는야 포켓몬 마스터

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

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

실버 4

자료구조, 해시를 사용한 집합과 맵

---

접근

포켓몬 이름에 대한 리스트를 먼저 만들고, 내가 문자를 입력하면 해당 포켓몬의 인덱스값 + 1을 출력하고, 숫자를 입력하면 숫자 -1의 인덱스에 위치한 포켓몬의 이름을 출력하도록 하고 싶었다.

 

파이썬에서는 input()이든 sys.stdin.readline()을 쓰든 내가 어떤 값을 입력하더라도 문자열로 인식하기 때문에

isdigit()함수를 사용해서 실제로 내가 입력한 값이 문자인지 숫자인지를 따로 판별할 수 있도록 할 수 있었다.

 

실패한 코드

import sys ; input = sys.stdin.readline
N, M = map(int, input().split())
pok = [input().rstrip() for _ in range(N)]

for _ in range(M):
    sol = input().rstrip()
    if sol.isdigit() == True:
        print(pok[int(sol)-1])
    else:
        print(pok.index(sol)+1)

 

시간 초과로 실패한 코드이다.

isdidit()는 시간복잡도가 O(n)이지만, 문제에서 입력하는 각각의 문자열의 최대 길이가 20이기 때문에 시간 초과와 큰 연관이 있어보이지는 않는다.

 

다만, 입력하는 포켓몬의 개수가 10만번까지의 범위이므로, 포켓몬의 정보를 담는 리스트가 길어지면 길어질수록

index()함수의 탐색 범위가 기하급수적으로 증가하게 된다.

(index()의 시간복잡도는 O(n)이기 때문)

 

이렇게 리스트의 범위가 큰 상황에서 인덱스 탐색이나 특정 문자를 탐색해야 할때, 시간 복잡도가 O(1)인 Dictionary를 이용하는 방법이 훨씬 빠르다.

 

성공한 코드

import sys ; input = sys.stdin.readline
N, M = map(int, input().split())
pok_int_key = {}
pok_name_key = {}

for i in range(N):
    name = input().rstrip()
    pok_int_key[i] = name
    pok_name_key[name] = i

for _ in range(M):
    sol = input().rstrip()
    if sol.isdigit() == True:
        print(pok_int_key[int(sol)-1])
    else:
        print(pok_name_key[sol]+1)