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

문제

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

풀이 1 (오답, 시간초과)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
names = [input().strip() for _ in range(N)]

for _ in range(M):
    q = input().strip()
    if q.isdigit():
        print(names[int(q) - 1])
    else:
        print(names.index(q) + 1)

• .index() 사용으로 인해 시간초과가 발생했다.
  • pokemons.index(q)는 names 리스트에서 q를 찾을 때까지 선형 탐색을 수행한다.
  • 시간 복잡도는 한번 탐색 시 O(N)이고, M번 반복되니 총 O(M*N)이다.

풀이 2

import sys
input = sys.stdin.readline

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

names = [input().strip() for _ in range(N)]
dic = {name: i+1 for i, name in enumerate(names)}

for _ in range(M):
    q = input().strip()
    if q.isdecimal():
        print(names[int(q) - 1])
    else:
        print(dic[q])

• .index() 사용을 피하기 위해 names 리스트와 더불어 dic 딕셔너리를 사용하기로 했다.
  • names: 포켓몬 이름을 저장한 list
    e.g. names = ['Bulbasaur', 'Ivysaur', ...]
  • dic: 포켓몬 이름: 번호로 저장한 dictionary
    e.g. dic = {'Bulbasaur': 1, 'Ivysaur': 2, ...}
• 또한 .isdigit() 대신 isdecimal()을 사용했다.
  • isdigit(): 숫자처럼 생긴 모든 글자를 숫자로 침.
  • isdecimal(): int형으로 변환 가능한지 확인
• 다만 비슷한 역할을 하는 변수가 두 개 쓰여서 별로인 것 같다.

풀이 3 (코딩공부를 하자님 풀이)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
dic = {}

for i in range(1, N+1):
    name = input().strip()
    dic[name] = i
    dic[i] = name

for _ in range(M):
    q = input().strip()
    if q.isdecimal():
        print(dic[int(q)])
    else:
        print(dic[q])

• dic 안에 포켓몬 이름: 번호, 번호: 포켓몬 이름으로 저장하였다.
• 메모리, 시간 면에서 풀이 2보다 비효율적이지만, 변수를 하나만 써서 논리적으로도, 이해하기도 더 좋은 것 같다.

---

오늘의 교훈

• .index() 대신 dictionary를 이용하자.
• .isdecimal(), .isdigit(), .isnumeric()은 다르다.
  • isdeciaml(): 문자열이 10진수 숫자로만 이루어져 있는지를 판별
  • isdigit(): 문자열이 유니코드 숫자로만 이루어져 있는지를 판별
  • isnuemric(): 숫자로 인정되는 유니코드 문자들을 모두 허용
    -> 즉, 해당 문자열을 int로 변환 가능한지 확인하려면 .isdecimal()을 사용하자.

참고 자료

• [Python] isdigit(), isdecimal(), isnumeric() 차이
  -> 이 시리즈에 있는 글 전부 유익하니 정독하는걸 추천한다.