존재 여부만 필요
중복 확인, 방문 체크처럼 key만 있으면 충분하다.
키를 만든 뒤 필요한 정보량으로 구조를 고른다
빈도 문제에서 key는 공유하지만, 저장해야 할 값의 양이 Map, Set, Heap, Window를 가른다.
key별 값이 필요
count, last index, sum처럼 key에 붙는 값을 저장한다.
상위 K개만 유지
Map 결과 전체를 정렬하지 않고 K개 후보만 남긴다.
오래된 키를 제거
무한 입력에서 메모리 상한을 유지하려면 만료 기준을 둔다.
| 질문 | 선택 | 예시 상태 |
|---|---|---|
| 이미 본 key인가? | Set | seen.has(key) |
| 몇 번 나왔나? | Map | freq[key] += 1 |
| K개만 필요한가? | Map + Heap | heap.size <= K |
| 입력이 계속 들어오나? | Map + Window | expire(oldKey) |
결론: key를 먼저 고정하고, 저장할 값의 양과 보존 기간을 기준으로 구조를 고른다.