[python]1620_나는야 포켓몬 마스터 이다솜

1. 사용한 자료구조 및 개념 : 딕셔너리

---

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ 포켓몬 리스트 입력값을 받아 포켓몬 이름과 인덱스 값을 매핑하여 딕셔너리에 저장한다.

2️⃣ 문제의 입력값들을 받아 .isdigit() 메서드를 활용하여 숫자이면 포켓몬 이름을 출력하고 문자열이면 해당 포켓몬 이름의 인덱스를 출력한다.

---

👻 어려웠던 점

🚨 시간초과

import sys

n, m = map(int, sys.stdin.readline().split())
pokemon = [0]

for _ in range(n):
    pokemon.append(sys.stdin.readline().strip())

for _ in range(m):
    q = input().strip()
    if q.isdigit():
        print(pokemon[int(q)])
    else:
        print(pokemon.index(q))

❓이유

: pokemon.index(q) 부분의 index() 메서드는 리스트의 처음부터 끝까지 순회하여 해당 요소의 인덱스를 찾는 연산을 수행한다. 이 과정은 O(N)시간이 소요되고 이 과정이 m번 수행되기 때문에 O(N*M)의 시간 복잡도가 발생하게 된다.

 

❗해결

: pokemon을 리스트가 아닌 딕셔너리로 선언하여 포켓몬 이름과 번호를 매핑하여 입력값을 저장한다. 포켓몬 이름이나 번호에 따라 딕셔너리에서 바로 조회할 수 있게한다.

---

Solution Code & 주석

import sys

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

for idx in range(1, n + 1):
    temp = sys.stdin.readline().strip()
    pokemon[idx] = temp
    pokemon[temp] = idx

for _ in range(m):
    q = sys.stdin.readline().strip()
    if q.isdigit():
        print(pokemon[int(q)])
    else:
        print(pokemon[q])