HashSet

도입

“빠르게 있는지 확인하고, 중복을 제거하고, 방문 여부를 기록하는” 문제를 푸는 핵심 도구다

코딩테스트에서 HashSet은 단순히 중복을 허용하지 않는 자료구조가 아니라, 존재 여부를 O(1)에 가깝게 확인하는 문제 해결 패턴으로 매우 자주 등장합니다. 어떤 값을 이미 봤는지 확인하거나, 중복을 제거하거나, 방문 여부를 기록하거나, 특정 조건을 만족하는 값이 존재하는지 즉시 판단해야 하는 문제는 HashSet으로 매우 효율적으로 풀 수 있습니다.

특히 자바에서는 HashSet, LinkedHashSet, TreeSet을 상황에 맞게 선택하고, add, contains, remove, retainAll, removeAll 같은 메서드를 정확히 활용하면 코드가 짧아지고, 중복 처리 실수나 탐색 시간 초과를 크게 줄일 수 있습니다.

필요성

HashSet을 잘 쓰면 중복 검사나 존재 확인 문제를 O(n²)에서 O(n) 수준으로 줄일 수 있는 경우가 많다

배열이나 리스트만으로 어떤 값이 이미 있는지 확인하려면 매번 선형 탐색이 필요해지는 경우가 많습니다. 하지만 HashSet을 사용하면 “이미 본 값인가?”, “이 값이 존재하는가?”를 매우 빠르게 판단할 수 있어서 시간 복잡도를 크게 줄일 수 있습니다.

HashSet이 강한 문제 유형

• 중복 원소 검사
• 서로 다른 원소 개수 구하기
• 방문 여부 기록
• 두 수의 존재 여부 확인
• 슬라이딩 윈도우 내 중복 제거
• 집합 연산
• 그래프 / DFS / BFS 방문 체크

구현체 선택

코딩테스트에서는 대부분 HashSet이 기본이고, 순서 유지나 정렬이 필요할 때만 다른 Set 구현체를 의심하면 된다

구현체	언제 쓰나
HashSet	대부분의 일반적인 존재 확인 / 중복 제거 문제
LinkedHashSet	입력 순서를 유지하면서 중복만 제거해야 할 때
TreeSet	정렬된 상태, 최소값 / 최대값, 범위 탐색이 바로 필요할 때

자주 쓰는 메서드

add, contains, remove, size를 익혀두면 HashSet 문제 풀이가 훨씬 짧고 명확해진다

set.add(value);         // 값 추가, 이미 있으면 false 반환
set.contains(value);    // 값 존재 여부 확인
set.remove(value);      // 값 제거
set.size();             // 원소 개수 확인
set.clear();            // 전체 비우기

실전 팁

add()는 단순 추가 메서드가 아니라 중복 여부를 즉시 판별하는 메서드이기도 합니다. 이미 존재하면 false를 반환하므로, 중복 체크를 한 줄로 처리할 수 있습니다.

패턴 1. 중복 검사

가장 많이 나오는 HashSet 패턴은 “이미 본 값인지 즉시 확인하는” 중복 검사다

배열이나 문자열에서 같은 값이 한 번이라도 다시 등장하는지 확인하는 문제는 거의 항상 HashSet으로 풀 수 있습니다.

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

for (int num : nums) {
    if (!seen.add(num)) {
        System.out.println("중복 발견");
        break;
    }
}

자주 나오는 문제 형태

• 배열에 중복이 있는지 판별하기
• 문자열에서 중복 문자 존재 여부 확인
• 한 번 본 값을 다시 만나면 종료하는 문제
• 방문한 노드 재방문 여부 검사

패턴 2. 존재 여부 확인

어떤 값이 집합 안에 존재하는지만 중요할 때는 HashSet이 가장 직접적인 해법이 된다

특정 수가 있는지, 어떤 문자열이 사전에 포함되는지, 방문한 적 있는 위치인지처럼 값의 존재 자체만 중요하면 Map보다 HashSet이 더 단순하고 자연스럽습니다.

Set<String> dict = new HashSet<>(wordList);

if (dict.contains(target)) {
    System.out.println("존재함");
}

패턴 3. 중복 제거와 고유 개수 세기

원소의 중복을 제거하거나 서로 다른 값의 개수를 구할 때는 HashSet이 가장 간결하다

중복을 제거한 결과가 필요하거나, 서로 다른 값의 수만 구하면 되는 문제는 HashSet에 모두 넣고 size()를 확인하는 방식이 매우 자주 쓰입니다.

Set<Integer> unique = new HashSet<>();

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

int answer = unique.size();

관련 문제 유형

• 서로 다른 원소 개수 구하기
• 폰켓몬 / 선택 가능한 종류 수 구하기
• 중복 제거 후 출력하기
• 유니크한 문자열 개수 세기

패턴 4. 짝 존재 여부 / Two Sum 변형

인덱스가 아니라 “그 값이 존재하는가”만 중요하면 HashSet으로 대표적인 O(n) 풀이가 가능하다

두 수의 합이 특정 값을 만들 수 있는지, 현재 값의 보완값이 이전에 존재했는지만 확인하면 되는 문제는 HashSet만으로도 충분합니다.

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

for (int num : nums) {
    int need = target - num;

    if (seen.contains(need)) {
        return true;
    }

    seen.add(num);
}

return false;

이 패턴은 두 수의 합뿐 아니라, 차이, 반대 부호 값, 특정 간격만큼 떨어진 수의 존재 여부를 찾는 문제에도 자주 응용됩니다.

패턴 5. 슬라이딩 윈도우 + 중복 제거

구간 안에 중복이 없어야 하는 문제는 HashSet과 투 포인터를 결합하면 강력해진다

현재 구간에 어떤 값이 포함되어 있는지만 관리하면 되는 문제는 HashSet과 투 포인터 조합으로 효율적으로 풀 수 있습니다. 특히 “중복 없는 가장 긴 부분 구간” 유형에서 매우 자주 등장합니다.

Set<Character> window = new HashSet<>();
int left = 0;
int answer = 0;

for (int right = 0; right < s.length(); right++) {
    while (window.contains(s.charAt(right))) {
        window.remove(s.charAt(left++));
    }
    window.add(s.charAt(right));
    answer = Math.max(answer, right - left + 1);
}

관련 문제 유형

• 중복 없는 가장 긴 부분 문자열
• 서로 다른 원소만 포함하는 최대 구간
• 윈도우 안 중복 허용 불가 문제

패턴 6. 방문 여부 기록

그래프 탐색이나 시뮬레이션에서는 “이미 방문했는가”를 저장하는 용도로 HashSet이 자주 쓰인다

노드 번호, 좌표, 상태값처럼 방문 여부만 기록하면 되는 경우에는 boolean 배열 대신 HashSet이 더 유연할 수 있습니다. 특히 상태 공간이 크거나 좌표가 음수를 포함할 때 유용합니다.

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

Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0});
visited.add("0,0");

while (!q.isEmpty()) {
    int[] cur = q.poll();

    for (int[] next : getNext(cur)) {
        String key = next[0] + "," + next[1];
        if (visited.add(key)) {
            q.offer(next);
        }
    }
}

패턴 7. 집합 연산

교집합, 합집합, 차집합 문제는 HashSet을 그대로 문제 모델로 삼으면 가장 깔끔하게 풀린다

문제 자체가 집합 개념으로 주어지는 경우에는 HashSet을 직접 쓰는 것이 가장 자연스럽습니다. 문자열 목록, 사용자 목록, 수의 집합을 비교하는 문제에서 매우 자주 보입니다.

Set<String> a = new HashSet<>(listA);
Set<String> b = new HashSet<>(listB);

Set<String> intersection = new HashSet<>(a);
intersection.retainAll(b);   // 교집합

Set<String> diff = new HashSet<>(a);
diff.removeAll(b);           // 차집합

관련 문제 유형

• 두 배열의 교집합 구하기
• 서로 다른 사용자 목록 비교
• 듣도 못한 사람 / 보도 못한 사람 찾기
• 집합 차이 계산

패턴 8. 순서 유지 또는 정렬된 Set 관리

중복 제거만이 아니라 출력 순서가 중요하면 LinkedHashSet이나 TreeSet으로 사고를 확장해야 한다

HashSet은 순서를 보장하지 않기 때문에, 입력 순서 유지가 필요하면 LinkedHashSet, 자동 정렬이 필요하면 TreeSet을 선택해야 합니다. 이 구현체 선택 하나로 코드가 훨씬 간결해지는 경우가 많습니다.

Set<String> ordered = new LinkedHashSet<>();
ordered.add("banana");
ordered.add("apple");
ordered.add("banana");

System.out.println(ordered); // [banana, apple]

TreeSet<Integer> sorted = new TreeSet<>(numsSet);
System.out.println(sorted.first());
System.out.println(sorted.last());

패턴 9. 문자열 문제

문자열 문제에서 HashSet은 중복 문자 검사, 부분 문자열 관리, 사전 집합 구성에 자주 쓰인다

• 중복 문자 확인 → 문자 Set
• 사전 단어 포함 여부 → 문자열 Set
• 윈도우 내 유니크 문자 관리 → 슬라이딩 윈도우 + Set
• 문자열 목록 중 중복 제거 → HashSet

패턴 10. 배열 / 리스트를 Set으로 바꿔서 푸는 전처리

입력 데이터를 먼저 Set으로 변환해 두면 이후 로직이 훨씬 단순해지는 경우가 많다

처음부터 Set으로 문제를 바라보면 쉬운 경우가 많습니다. 리스트를 계속 순회하기보다, 한 번 Set으로 바꿔 놓고 빠르게 조회하는 방식으로 풀이 전체를 단순화할 수 있습니다.

Set<Integer> numSet = Arrays.stream(nums)
    .boxed()
    .collect(Collectors.toSet());

for (int query : queries) {
    System.out.println(numSet.contains(query));
}

자주 하는 실수

코딩테스트에서 HashSet 문제를 틀리는 이유는 대개 순서 착각, remove 타이밍 실수, 객체 비교 문제 때문이다

• HashSet이 입력 순서를 보장한다고 착각함 → 필요하면 LinkedHashSet 사용
• 정렬된 결과가 필요한데 HashSet만 사용하고 출력 순서를 처리하지 않음
• 슬라이딩 윈도우에서 remove 시점을 잘못 잡아 로직이 꼬임
• contains() 대신 리스트 탐색을 계속해서 시간 초과가 남
• 사용자 정의 객체를 Set에 넣으면서 equals(), hashCode()를 올바르게 구현하지 않음
• 중복 개수가 필요한데 Set만 써서 빈도 정보가 사라짐 → 이런 경우는 Map이 더 적합

풀이 루틴

문제를 보면 “값의 존재만 중요할지, 개수나 위치도 필요한지”부터 먼저 구분하는 습관이 중요하다

1. 중복 허용 여부가 핵심인지 먼저 본다.
2. 존재 여부만 필요하면 Set을 먼저 의심한다.
3. 개수, 인덱스, 부가 정보까지 필요하면 Map이 더 적합한지 확인한다.
4. 정렬이 필요 없으면 우선 HashSet부터 생각한다.
5. 입력 순서 유지가 필요하면 LinkedHashSet, 정렬이 필요하면 TreeSet으로 확장한다.

디버깅

HashSet 풀이가 틀릴 때는 비교 기준, remove 조건, 순서 요구사항, 자료구조 선택을 먼저 확인해야 한다

1

정말 필요한 정보가 존재 여부뿐인지, 아니면 개수나 위치까지 필요한지 다시 확인한다.

2

슬라이딩 윈도우 문제라면 값을 제거하는 시점이 정확한지 확인한다.

3

출력 순서가 중요한데 HashSet을 써서 결과가 흔들리는 것은 아닌지 점검한다.

4

사용자 정의 객체를 넣었다면 equals()와 hashCode() 구현을 반드시 확인한다.

5

Set이 아니라 Map이나 배열 카운팅이 더 적합한 문제는 아닌지도 함께 본다.

요약

코딩테스트에서 HashSet은 “존재 확인”, “중복 제거”, “방문 기록”, “집합 연산” 문제를 빠르게 푸는 가장 중요한 도구 중 하나다

• ✅ HashSet은 코딩테스트에서 중복 검사와 존재 확인을 O(n) 수준으로 줄이는 핵심 도구가 될 수 있다.
• ✅ 기본 구현체는 HashSet, 순서 유지가 필요하면 LinkedHashSet, 정렬이 필요하면 TreeSet을 고려한다.
• ✅ 중복 제거, 방문 체크, 슬라이딩 윈도우, 집합 연산 문제에서 매우 자주 등장한다.
• ✅ add(), contains(), remove(), size()를 정확히 이해하면 코드가 짧고 명확해진다.
• ✅ 문제를 보면 “존재만 중요할지, 개수나 위치도 필요한지”부터 구분하는 습관이 중요하다.