[코딩테스트] 2. HashSet 활용 패턴

HashSet은 "값이 있는지 빠르게 확인한다"는 목적에 가장 잘 맞는다. 코딩테스트에서는 보통 중복, 방문, 포함 여부 문제에서 등장한다.

패턴 하나 중복 제거

서로 다른 값의 개수가 필요할 때 쓴다.

int[] nums = {3, 1, 2, 3};
Set<Integer> set = new HashSet<>();

for (int num : nums) {
    set.add(num);
}

int uniqueCount = set.size();

대표적인 사고 흐름은 다음이다.

질문	판단
중복은 한 번만 세면 되나	HashSet
중복 횟수도 필요하나	HashMap

패턴 둘 방문 여부

이미 방문한 상태를 다시 처리하지 않기 위해 사용한다.

Set<String> visited = new HashSet<>();

String state = row + "," + col;
if (!visited.contains(state)) {
    visited.add(state);
    // 다음 처리
}

격자 좌표, 문자열 상태, 조합 상태 등을 한 번만 처리해야 할 때 유용하다.

패턴 셋 빠른 포함 여부 확인

한 목록에 있는 값을 기준으로 다른 목록을 검사할 때 사용한다.

Set<String> words = new HashSet<>(Arrays.asList(dictionary));

for (String query : queries) {
    if (words.contains(query)) {
        answer++;
    }
}

ArrayList.contains는 선형 탐색이라 O(N)이다. 조회가 많이 반복되면 먼저 HashSet으로 바꾸는 것이 좋다.

구조	contains
ArrayList	O(N)
HashSet	평균 O(1)

패턴 넷 교집합과 차집합

두 집합의 공통 원소나 한쪽에만 있는 원소를 찾을 때도 쓴다.

Set<String> a = new HashSet<>(Arrays.asList("a", "b", "c"));
Set<String> b = new HashSet<>(Arrays.asList("b", "c", "d"));

Set<String> intersection = new HashSet<>(a);
intersection.retainAll(b); // b, c

Set<String> difference = new HashSet<>(a);
difference.removeAll(b); // a

다만 removeAll, retainAll은 문제에서 중복 개수가 중요한 경우에는 맞지 않는다. 집합 연산은 "존재 여부" 기준이다.

패턴 다섯 처음 보는 값만 처리

중복 입력 중 처음 등장한 값만 처리하고 싶을 때 add의 반환값을 활용한다.

Set<String> seen = new HashSet<>();

for (String name : names) {
    if (seen.add(name)) {
        // 처음 등장한 name
    }
}

add는 값이 새로 추가되면 true, 이미 있으면 false를 반환한다.

자주 틀리는 장면

개수가 필요한데 HashSet을 쓴다

HashSet은 중복을 버린다. 따라서 다음 문제에는 직접적인 정답 구조가 아니다.

participant = ["mislav", "stanko", "mislav", "ana"]
completion  = ["stanko", "ana", "mislav"]

여기서 "mislav"는 참가자에 2번, 완주자에 1번 등장한다. HashSet은 "mislav"를 1개만 저장하므로 이 차이를 표현하지 못한다.

순서가 필요한데 HashSet을 쓴다

HashSet은 순서가 없다. 출력 순서가 중요하면 ArrayList와 정렬, LinkedHashSet, TreeSet 등을 고려해야 한다.

contains가 많아도 원본을 계속 ArrayList로 둔다

조회가 반복되면 ArrayList.contains가 병목이 된다.

// 느려질 수 있는 방식
for (String q : queries) {
    if (list.contains(q)) {
        count++;
    }
}

조회 대상이 고정되어 있으면 먼저 HashSet으로 바꾼다.

Set<String> set = new HashSet<>(list);
for (String q : queries) {
    if (set.contains(q)) {
        count++;
    }
}

판단 체크리스트

• 값의 존재 여부만 필요한가
• 중복 개수는 버려도 되는가
• 출력 순서가 중요하지 않은가
• contains를 많이 호출하는가
• 방문 여부를 빠르게 확인해야 하는가

대부분 예라면 HashSet을 고려한다.

---