자바 - HashSet으로 코테 푸는 법

코딩 테스트에서 Set과 특히 HashSet을 사용하는 경우와 대표적인 유형들을 자세히 살펴보겠습니다. Set은 중복을 허용하지 않는 자료구조이며, HashSet은 이 중에서도 해시 테이블을 기반으로 구현되어 있어 특히 조회, 추가, 삭제 작업에서 빠른 성능을 제공합니다.

1. 코테에서 Set을 사용해야 하는 경우

Set은 주로 다음과 같은 상황에서 유용합니다:

• 중복 제거: 데이터 컬렉션에서 중복된 요소를 제거해야 할 때.
• 존재 여부 확인: 특정 요소가 데이터 컬렉션 내에 존재하는지 빠르게 확인할 때.
• 집합 연산: 다른 컬렉션과의 합집합, 교집합, 차집합을 구할 때.

2. 대표적인 Set 써야 하는 유형

• 유일한 요소 찾기: 배열이나 리스트에서 모든 중복을 제거하고 유일한 요소만을 유지해야 하는 문제.
• 공통 요소 탐색: 두 개 이상의 데이터 컬렉션에서 공통으로 포함된 요소를 찾는 문제.
• 데이터 집합 간의 관계 분석: 여러 데이터 집합 간의 관계를 분석하여 특정 조건을 만족하는 요소를 찾거나 연산을 수행하는 문제.

3. 코테에서 HashSet을 사용해야 하는 경우

HashSet은 Set 인터페이스의 일반적인 사용 사례에 추가하여, 특히 다음과 같은 경우에 적합합니다:

• 높은 성능 요구: 요소의 추가, 삭제, 조회 등의 작업을 O(1) 평균 시간 복잡도로 처리해야 할 때.
• 큰 데이터 처리: 큰 데이터 컬렉션을 처리하면서 중복을 제거하거나 특정 요소의 존재를 빠르게 확인해야 할 때.

4. 대표적인 HashSet 써야 하는 유형

• 중복 문자 없는 최대 부분 문자열: 문자열에서 중복 문자가 없는 가장 긴 부분 문자열을 찾는 문제.
• 주어진 합을 만들 수 있는 두 숫자 찾기: 배열에서 두 수를 선택해 특정 합을 만족하는지 확인하는 문제.
• 중복 요소 탐색: 배열이나 리스트에서 중복 요소가 있는지 빠르게 확인하는 문제.

HashSet을 사용하는 경우에는 요소의 해시 가능성이 좋고, 해시 충돌이 최소화되는 조건에서 특히 효과적입니다. 데이터의 유일성을 보장하면서 빠른 성능을 필요로 하는 다양한 코딩 테스트 문제에서 HashSet은 매우 강력한 도구가 될 수 있습니다.

---

HashSet을 사용하여 푸는 코딩 테스트 문제

문제: 중복 문자 없는 가장 긴 부분 문자열 찾기

문제 설명: 주어진 문자열에서 중복 문자가 없는 가장 긴 부분 문자열의 길이를 찾아 반환합니다.

예시:

• 입력: "abcabcbb"
• 출력: 3 (해답은 "abc", 중복 없는 가장 긴 부분 문자열)

솔루션 코드

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int maxLength = 0;
        int i = 0, j = 0;

        while (j < s.length()) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                maxLength = Math.max(maxLength, set.size());
            } else {
                set.remove(s.charAt(i++));
            }
        }

        return maxLength;
    }
}

코드 설명

• 두 포인터 i와 j를 사용하여 슬라이딩 윈도우를 구현합니다.
• j 포인터는 현재 탐색 중인 문자를 가리키고, 이 문자가 HashSet에 없다면 추가하고 j를 증가시킵니다.
• 중복 문자가 발견되면, i 포인터가 가리키는 문자를 HashSet에서 제거하고 i를 증가시킵니다.
• 이 과정을 통해 HashSet에는 항상 중복 없는 문자만이 저장됩니다.
• 각 단계에서의 HashSet 크기가 중복 없는 부분 문자열의 최대 길이가 됩니다.