백준 1620번: 나는야 포켓몬 마스터 - 파이썬

백준 1620번: 나는야 포켓몬 마스터 (www.acmicpc.net/problem/1620)

 

💡접근

• 시간 제한 : 2초
• 포켓몬을 리스트에 저장하고, 숫자로 변환 가능한 경우 index-1로 검색, 숫자로 변환 가능하지 않은 경우는 이름으로 index 검색하자.
• isdigit() 함수의 시간복잡도는 O(n)이다 → 한 문자열의 최대 길이가 20이니까, 최악의 경우 20x10만 = 200만이다. (이 함수는 시간초과랑 크게 관련 없을듯)
• 풀이코드1번으로 하니까 시간초과가 났는데, index 함수의 시간복잡도는 O(n)이기 때문에, 10만개의 포켓몬들 중에서 찾을때는 최악의 경우 매번 10만번을 탐색한다..
• 즉 10만x10만 = 100억번.
• 그럼 데이터 읽기 부분을 어떻게 개선 시킬 수 있을까? → 해쉬 자료구조의 경우 O(1)이 걸린다고 했으니 이것을 활용해봐야겠다.

 

💡배운점 및 오답 원인

• 리스트에서 탐색을 할 경우 시간복잡도는 O(n)이다. 따라서 index를 탐색할 때, 데이터의 양에 따라 적합하지 않을 수 있으니 자료구조별로 시간 복잡도를 잘 생각해야겠다.
• Python dictionary는 hash table을 사용한것으로써, 읽을때 시간복잡도가 O(1)이다.
• 인덱스 탐색이나 특정 문자 탐색을 할 때, dictionary를 사용하는 것이 유리할 수 있다!
  • ⚠️ Hash 자료구조에 대해서 정리하기
  • Python dictionary에 대한 참고자료 : How are Python's Built In Dictionaries Implemented?

 

💡풀이 코드 1 (시간초과)

import sys

n, m = map(int, input().split())

# 리스트에 포켓몬 저장
poketlist = []
for i in range(n):
    temp = sys.stdin.readline().strip()
    poketlist.append(temp)

# 포켓몬 탐색
for _ in range(m):
    item = sys.stdin.readline().strip()
    # 입력값이 int일 경우
    if item.isdigit() == True:  # isdigit -> O(n)
        print(poketlist[int(item)-1])
    # 입력값이 int가 아닐 경우 (문자열일경우)
    else:
        print(poketlist.index(item))

 

💡풀이 코드 2 (자료구조 개선 - 리스트에서 dictionary로!)

import sys

n, m = map(int, input().split())

# 리스트에 포켓몬 저장
pokedic_int_key = {}  # Key값이 int인 dictionary
pokedic_name_key = {}  # Key값이 str인 dictionary
for i in range(n):
    name = sys.stdin.readline().strip()
    pokedic_int_key[i] = name
    pokedic_name_key[name] = i

# 포켓몬 탐색
for _ in range(m):
    item = sys.stdin.readline().strip()
    # 입력값이 int일 경우, key값이 int인 dictionary에서 value를 가져옴
    if item.isdigit() == True:  # isdigit -> O(n)
        print(pokedic_int_key[int(item)-1])
    # 입력값이 int가 아닐 경우 (문자열일경우), key값이 str인 dictionary에서 value를 가져옴
    else:
        print(pokedic_name_key[item]+1)