1. 문제 소개

알고리즘 인터뷰와 프로그래밍 연습에서 자주 등장하는 **두 수의 합(Two Sum)**과 **세 수의 합(3Sum)**은 배열 처리 문제로, 기본적인 알고리즘 능력을 평가하고 효율적인 검색 기법을 이해하는 데 중요한 역할을 합니다. 이 문서에서는 두 문제를 Java로 구현하고 최적화 방법을 설명합니다.

2. 두 수의 합(Two Sum)

2.1 문제 설명

배열에서 특정한 두 숫자의 합이 주어진 값(target)이 되도록 하는 인덱스를 찾아야 합니다.

2.2 해시 테이블 활용

코드 예제

import java.util.HashMap;
import java.util.Map;

public class TwoNumberSum {
    public int[] findTwoSum(int[] numbers, int targetValue) {
        Map<Integer, Integer> numberMap = new HashMap<>();
        
        for (int index = 0; index < numbers.length; index++) {
            int complementValue = targetValue - numbers[index];
            if (numberMap.containsKey(complementValue)) {
                return new int[] { numberMap.get(complementValue), index };
            }
            numberMap.put(numbers[index], index);
        }
        return new int[0];
    }
}

중요 포인트

복잡도 비교

3. 세 수의 합(3Sum)

3.1 문제 설명

배열에서 세 숫자의 합이 0이 되는 조합들을 모두 찾습니다.

3.2 정렬 + 투포인터 접근

코드 예제

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeNumberSum {
    public List<List<Integer>> findThreeSum(int[] numbers) {
        List<List<Integer>> result = new ArrayList<>();
        if (numbers == null || numbers.length < 3) return result;
        Arrays.sort(numbers); // 필수 사전 처리
        
        for (int i = 0; i < numbers.length - 2; i++) {
            if (i > 0 && numbers[i] == numbers[i - 1]) continue; // 중복 제거
            if (numbers[i] > 0) break; // 더 이상 가능한 조합 없음
            
            int leftPointer = i + 1, rightPointer = numbers.length - 1;
            while (leftPointer < rightPointer) {
                int total = numbers[i] + numbers[leftPointer] + numbers[rightPointer];
                if (total == 0) {
                    result.add(Arrays.asList(numbers[i], numbers[leftPointer], numbers[rightPointer]));
                    while (leftPointer < rightPointer && numbers[leftPointer] == numbers[leftPointer + 1]) leftPointer++;
                    while (leftPointer < rightPointer && numbers[rightPointer] == numbers[rightPointer - 1]) rightPointer--;
                    leftPointer++;
                    rightPointer--;
                } else if (total < 0) {
                    leftPointer++; // 더 큰 값을 필요로 함
                } else {
                    rightPointer--; // 더 작은 값을 필요로 함
                }
            }
        }
        return result;
    }
}

중요 포인트

복잡도 분석

4. 비교 요약

5. FAQ

Q1: 세 수의 합에서 왜 정렬이 필요한가요? 정렬하면 시간 복잡도를 O(n³)에서 O(n²)로 줄일 수 있고, 중복 요소를 쉽게 건너뛸 수 있습니다.

Q2: 입력 배열의 중복 요소는 어떻게 처리하나요?

• 외부 루프에서 동일한 시작 요소 스킵
• 유효한 조합 발견 후 내부 루프에서 포인터 값 중복 스킵

Q3: 왜 해시 테이블이 세 수의 합에 적합하지 않은가요? 해시 테이블은 두 수의 합을 저장할 수 있지만, 중복 처리가 어려우며 공간 복잡도가 증가합니다.