(Day1) Hash

1. 기록 필요한 내용 정리

1. 해시란?

• key-value 자료구조
• like 전화번호부 (이름-번호)

• •  

2. 해시 언제 사용?

• String 기반으로 정보를 기록하고 관리해야 할 때
  • 이땐 단순배열을 쓸 수 없으니 hash를 활용하자
  • → 대부분의 경우 해시의 key가 string이다

3. 파이썬에선?

• 파이썬에서는 dictionary라는 HashMap이 존재

1. 선언

map = dict()

 

2. 삽입

map[key] = value

 

3. 탐색

 

(1) 키 탐색

if key in map: #key가 map에 존재한다면 true

 

(2) 값 탐색

if value in map.values(): #value가 map에 존재하면 true

 

4. 삭제

d.pop(key) # key에 해당하는 값 삭제하고 그 값 반환

 

 

5. defaultdict

defaultdict를 사용하면 키 값 존재 여부를 확인할 필요가 없도록 default 값을 설정할 수 있다.

해당 키 값이 없으면 default로 설정해둔 값이 자동으로 저장된다.

 

(1) 선언

from collections import defaultdict

map = defaultdict(lambda : 0) # lambda : default 로 초기값을 정할 수 있다.

 

(ex) map에 아무것도 존재하지 않을 때 map["a"] += 1을 하면 자동으로 ( "a" - 0 )쌍을 만들어서 저장하고 여기에 1을 더한다.

 

 

(2) 사용 설명

from collections import defaultdict
# defaultdict는 외부 collections 라이브러리에서 가지고 와야함

d1 = defaultdict(int) 
# int를 기준으로 생성한 딕셔너리 d1의 값은 항상 0으로 자동 초기화
# ex. ('i', 4), ('m', 1), ('p', 2), ('s', 4) 

d2 = defaultdict(list) 
# list를 기준으로 생성한 딕셔너리 d2의 값은 항상 []으로 자동 초기화
# ex. ('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])

d3 = defaultdict(set)
# set을 기준으로 생성한 딕셔너리 d3의 값은 항상 {}으로 자동 초기화
# ex. ('blue', {2, 4}), ('red', {1, 3})

map = defaultdict(lambda : 0) 
# lambda : default 로 초기값을 정할 수 있다.

---

2. 문제 풀이 시작 전 구현 방식 참고

https://velog.io/@stella317/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%8B%A0%EA%B3%A0-%EA%B2%B0%EA%B3%BC-%EB%B0%9B%EA%B8%B0Python 

프로그래머스 - 신고 결과 받기[Python]

 

---

3. 실제로 푼 문제

(1) 폰켄몬

- 체감 난이도 :

최하 - 복습 필요 X

- 기억해야할 내용 :

중복을 없애야 할땐 set 사용

 

(2) 전화번호 목록

- 체감 난이도 :

중 - 해시문제라는걸 알기 어려움

- 기억해야할 내용 :

(1) 풀이 1

list of strings를 sort 하면 어떻게 되는지. 를 알고 있으면 쉽게 풀 수 있음.

prefix substring 관련해서는 string sort()를 통해 쉽게 해결 가능하다는 것을 기억!

(2) 풀이 2

set 사용해서 풀이 가능

 

 

(3)

- 체감 난이도 :

- 기억해야할 내용 :

 

 

---

4. 참고한 자료

https://www.youtube.com/watch?v=zFL29ydL9D8