[코드트리 조별과제] 딕셔너리 (Python) - 8월 2주차

👀  Dictionary

 

 

https://www.codetree.ai/missions/8/problems/hashmap-basic/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

시간초과 날 것 같으면 무조건 떠올리게 되는 딕셔너리에 대해 알아본다. 

파이썬의 dict는 HashMap 자료구조로 되어있고, 데이터를 (key, value) 쌍 형태로 관리한다. 

HashMap의 가장 큰 특징은 1) 순서가 없고 2) key로 value에 접근하는 시간복잡도가 매우 작다. 

다음 링크의 게시물을 참고했을 때 시간복잡도는 Access에 N/A, Search에 O(1)이다. 

 

https://paulonteri.com/dsa/ds&a/time-and-space-complexity

Complexity Analysis & Big O | DSA | PaulOnteri.com

 

 

다만, 해시 알고리즘을 기반으로 하기 때문에 관리해야 하는 메모리가 크다는 단점이 있다. 

그러나 코딩테스트에서는 보통 메모리보다 시간복잡도가 문제기 때문에 우선적으로 고려하게 되는 자료구조다.

 

 

 

 

 

 

대응되는 수와 문자 https://www.codetree.ai/missions/8/problems/corresponding-numbers-and-characters/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

제출한 코드

import sys

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

str_dict = {}
num_dict = {i:"" for i in range(1, n+1)}

for j in range(1, n+1):
    inputt = sys.stdin.readline().rstrip()
    str_dict[inputt] = j
    num_dict[j] = inputt
    
for _ in range(m):
    ii = sys.stdin.readline().rstrip()
    if ii.isdigit():
        print(num_dict[int(ii)])
    else:
        print(str_dict[ii])