[Python] 유사 딕셔너리 defaultfict()

defaultdict()

• 지정하지 않은 값은 빈자리로 두고 인덱스 지정해서 바로 추가 가능
• 인덱스 군데군데 삽입하고 싶을 때 사용 
• 딕셔너리를 만드는 dict 클래스의 서브 클래스
• 인자로 주어진 객체의 기본 값을 딕셔너리의 초기값으로 지정할 수 있다
• int, list, set 등이 가능

 

• 외부함수이므로 import 해줘야함

from collections import defaultdict

 

• defaultdict(int)
  • 지정하지 않은 키의 value는 0

 

• defaultdict(list)
  • 지정하지 않은 키의 value는 []
  • list 이므로 value값 추가 시 .append() 사용 가능

 

• defaultdict(set)
  • 지정하지 않은 키의 value는 {}
  • set이므로 value값 추가 시 .add() 사용 가능

from collections import defaultdict

wires=[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

data = defaultdict(set)  # 각 노드별 연결된 노드 정보
for a, b in wires:
    data[a].add(b)
    data[b].add(a)

 

---

defaultdict

딕셔너리는 키/값 (key / value)으로 이루어져 있는 자료구조이고 파이썬3.7이상의 버전부터는 순서가 입력한대로 유지된다. 내부는 해시테이블로 구현되어있다. 해시 테이블로 구현된 파이썬의 자료형을 제시하라는 질문을 받는다면 주저없이 딕셔너리라고 답할 수 있어야한다.

​

key에는 변화하는 값이 들어갈 수 없다. 따라서 가변적인 리스트list가 key가 될 수는 없지만 변하지 않는 튜플tuple은 key로 사용할 수 있다. 반대로 value에는 튜플과 리스트 관계없이 사용할 수 있다.

​

딕셔너리 주요 연산 시간 복잡도

연산	시간복잡도	설명
len(a)	O(1)	요소 개수 리턴
a[key]	O(1)	키 조회, value리턴
a[key] = value	O(1)	key, value값을 삽입
key in a	O(1)	딕셔너리에 해당 키가 있는지 확인

대부분의 연산이 O(1)로 처리되기 때문에 시간복잡도상 효율적인 자료형이다.

​

리스트 : 조회할 때 인덱스의 위치를 숫자로 입력. ex) list[0]

딕셔너리 : key값을 직접 입력 ex) dict['key']

​

딕셔너리에는 defaultdict 라는 모듈이 있어

딕셔너리의 값을 유연하게 삽입하는 데에 도움이 된다.

 

defaultdict 객체

리스트 : 존재하지 않는 인덱스 조회 시 IndexError

딕셔너리 : 존재하지 않는 키 조회 시 KeyError

Defultdict : KeyError를 출력하는 대신 정해져있는 기본 값을 기준으로 key값에 대한 딕셔너리의 요소를 생성해주는 기능

d = defaultdict(int)
d['A'] = 0
d['B'] = 1
d['C'] += 1

 

원래대로라면 'C'라는 key값이 없어서 += 1 의 연산을 수행하면 KeyError가 출력되어야 하지만

defaultdict(int)를 통해 정해져있는 기본값 0을 기준으로 1이 더해진 값 1이 'C'라는 key의 value로 딕셔너리에 삽입된다.

 

{'A' : 0 , 'B' : 1, 'C' : 1}

---

​딕셔너리 value값으로 리스트[] 넣기

defaultdict(list)를 이용하면 리스트형태로 value를 추가할 수 있다.

for i in range(len(list)):
	dict[list[i][1]] += [list[i][0]]

• 초기화 상태(디폴트)

from collections import defaultdict

d=defaultdict(list)
for i in range(5):
  print(d[i])
  
'''
[]
[]
[]
[]
[]
'''

• 입력값을 받아서 defaultdict에 넣을 경우

from collections import defaultdict

d=defaultdict(list)
for i in range(4):
  s,e=map(int,input().split())
  d[s].append(e)

for i in range(1,6):
  print(d[i])

'''
입력값 s,e
3 1
3 2
4 3
5 3
'''

'''
결과
[]
[]
[1, 2]
[3]
[3]
'''

 

defaultdict 에 2차원 배열 넣을 경우

from collections import defaultdict

d=defaultdict(list)
lst=defaultdict(list)
for i in range(4):
  s,e=map(int,input().split())
  d[s].append(lst[e])

for i in range(1,6):
  print(d[i])

'''
입력값 s,e
3 1
3 2
4 3
5 3

결과
[]
[]
[[], []]
[[]]
[[]]
'''

 

---

from collections import defaultdict

d=defaultdict(list)
lst=defaultdict(int)
for i in range(4):
  s,e=map(int,input().split())
  d[s].append(lst[e])

for i in range(1,6):
  print(d[i])

'''
입력값 s,e
3 1
3 2
4 3
5 3

결과
[]
[]
[0, 0]
[0]
[0]
'''