기준

Set은 존재 여부, Map은 매핑과 빈도다. "있다/없다"와 "몇 개 있다"를 구분하면 자료구조 선택이 쉬워진다.

선택 지도

flowchart TD Need["값을 기억해야 한다"] --> What{"무엇을 알아야 하나"} What -->|존재 여부| Set["Set"] What -->|개수| Count["Map 또는 int 배열"] What -->|값에 연결된 정보| Map["Map"] What -->|정렬된 순서| Tree["TreeSet TreeMap"] What -->|입력 순서| Linked["LinkedHashSet LinkedHashMap"]

Set으로 빈도를 추적

발생 장면

BOJ2531 회전 초밥에서 현재 윈도우에 어떤 초밥이 있는지만 저장하고, 몇 개 있는지를 놓쳤다.

Set은 중복을 지운다. 같은 번호가 2개 들어왔는지 1개 들어왔는지 알 수 없다.

Set<Integer> set = new HashSet<>();
set.add(7);
set.add(7);
set.size(); // 1

고치는 기준

int[] count = new int[d + 1];

if (count[sushi] == 0) {
    kind++;
}
count[sushi]++;

상세: Set으로 빈도 추적 시도

Map.get() 결과를 바로 연산

증상

처음 보는 key에서 null이 나와 NPE가 난다.

map.put(word, map.get(word) + 1);

고치는 기준

map.put(word, map.getOrDefault(word, 0) + 1);

빈도 누적은 getOrDefault()를 기본 형태로 둔다.

순서가 필요한데 HashSet을 사용

필요한 순서자료구조
순서 상관 없음HashSet, HashMap
정렬된 순서TreeSet, TreeMap
입력 순서LinkedHashSet, LinkedHashMap

HashSet은 순회 순서를 기대하면 안 된다.

객체 key에 동등성 기준이 없음

좌표나 상태 객체를 key로 쓰려면 equals()와 hashCode()가 필요하다.

record Pos(int row, int col) {
}

Java 버전이 허용되면 값 객체는 record가 깔끔하다. 그렇지 않으면 두 메서드를 직접 만든다.

containsValue()를 자주 호출

containsKey()는 평균 O(1)이지만 containsValue()는 값을 찾아 순회한다. 조회 기준이 value라면 자료구조 설계를 다시 본다.