[BOJ] 1620번: 나는야 포켓몬 마스터 이다솜 (python)

문제 링크 : https://www.acmicpc.net/problem/1620

문제넘길ㅇ..

💡 해결 방법

• 처음엔 그냥 list써서 입력하고, for문으로 list에 있는 값 찾으면 되는 문제인줄 알고 너무 쉽다고 생각했다.
• 하지만 리스트에서 탐색을 할 경우 시간복잡도는 O(n)이다.
• 따라서 index를 탐색할 때, 데이터의 양에 따라 적합하지 않을 수 있으니 자료구조별로 시간 복잡도를 잘 생각해야 한다.
  
  
• Python dictionary는 hash table을 사용한것으로써, 읽을때 시간복잡도가 O(1)이다.
• 인덱스 탐색이나 특정 문자 탐색을 할 때, dictionary를 사용하는 것이 유리할 수 있다.
  
  

🖥️ 내 코드 (오답)

import sys

N, M = map(int, sys.stdin.readline().split())
arr = 

for i in range(N):
    arr.append(sys.stdin.readline().rstrip())

for i in range(M):
    check = sys.stdin.readline().rstrip()
    if check.isnumeric():
        print(arr[int(check)-1])
    else:
        print(arr.index(check)+1)

🖥️ 정답코드

import sys

N, M = map(int, sys.stdin.readline().split())
intDic = {} #key값이 int인 dic
strDic = {} #key값이 str인 dic

for i in range(N):
    name = sys.stdin.readline().rstrip()
    intDic[i] = name
    strDic[name] = i

for i in range(M):
    check = sys.stdin.readline().rstrip()
    if check.isnumeric():
        print(intDic[int(check)-1])
    else:
        print(strDic[check]+1)

✏️ 알고리즘 분류

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