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