📌 "Key-Value 쌍으로 데이터를 빠르게 찾아보세요."
출제빈도 : 높음
평균점수 : 보통
해시(Hash)란?
- 데이터를 key-value 쌍으로 저장하는 자료구조
- 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 자료구조
- key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 시간복잡도가 평균적으로 O(1)이다.
- 파이썬의 '딕셔너리'가 바로 '해시'이다.
해시를 사용하면 좋은 경우
- 리스트를 쓸 수 없을 때
<=> 인덱스값을 숫자가 아닌 다른값(ex. 문자열, 튜플 등)으로 사용하려고 할때 - 빠른 접근/탐색이 필요할 때
- 집계가 필요할 때
코드
1. 전화번호 목록 (Lv. 2)
시간초과 때문에 애먹었는데 딱히 해시를 이용해 풀지도 않음.
해시를 사용한 정석 코드⬇️
2. 의상 (Lv. 2)
옷의 종류별로 가지고 있는 의상 개수에 1을 더해서(하나씩 고르거나 한개도 고르지 않는 경우) 모두 곱한 다음, 아무것도 선택하지 않은 한가지 경우의 수를 빼면 답이다. 이를 collections.Counter를 사용해서 계산했다.
3. 베스트앨범 (Lv. 3)
genres와 plays를 동시에 돌면서 장르별 노래의 재생횟수를 담은 딕셔너리를 만든다. 이 딕셔너리를 돌면서 각 장르별 '노래'를 재생횟수의 내림차순 & 고유번호의 오름차순으로 정렬한다. 그리고 장르별 노래들의 전체 재생횟수 내림차순으로 '장르'를 또 정렬한다.
정렬된 딕셔너리를 조건에 맞게 출력해낸다.
느낀점
- 데이터(value)에 key를 통해 빠르게 접근하는 것이 중요
- 다행히 파이썬이라서 딕셔너리를 잘 활용하면 어렵지 않게 풀 수 있는 자료구조다.
일기장같은 공부기록📝