2Sum과 3Sum 문제 접근 방법 및 시간복잡도 분석

코딩 테스트에서 자주 등장하는 문제 유형 중 하나가 2Sum과 3Sum 문제입니다.

이 문제들은 배열 내에서 특정 조건을 만족하는 숫자 조합을 찾는 문제로, 효율적인 접근 방식이 중요합니다.

---

🔹 1. 2Sum 문제 접근 방식

문제 개요:

• 주어진 정수 배열 nums에서, 두 숫자의 합이 target이 되는 인덱스 쌍을 찾는 문제입니다.
• 같은 요소를 두 번 사용할 수 없으며, 중복된 결과를 허용하지 않습니다.

접근 방식 및 시간복잡도: 1️⃣ Brute Force (완전 탐색) → O(N²)

• 모든 두 숫자의 조합을 확인하는 방법.
• ❌ O(N²)으로 입력 크기가 커지면 비효율적
• 코드 예시:

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

 

2️⃣ Hash Map을 활용한 최적화 → O(N)

• 배열을 순회하면서 target - 현재 값이 HashMap에 있는지 확인
• ✅ O(N) 시간복잡도, O(N) 공간복잡도
• 빠른 검색이 가능하여 가장 효율적인 방법
• 코드 예시:

function twoSum(nums: number[], target: number): number[] {
    let map = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement)!, i];
        }
        map.set(nums[i], i);
    }
    return [];
}

---

🔹 2. 3Sum 문제 접근 방식

문제 개요:

• 주어진 정수 배열 nums에서, 세 숫자의 합이 0이 되는 모든 조합을 찾는 문제.
• 같은 조합이 여러 번 나오지 않도록 해야 합니다.

접근 방식 및 시간복잡도: 1️⃣ Brute Force (완전 탐색) → O(N³)

• 모든 세 숫자의 조합을 탐색.
• ❌ 시간복잡도 O(N³) → 비효율적!

2️⃣ Two-Pointer + 정렬 → O(N²)

• 배열을 **정렬(O(N log N))**한 후, 하나의 값을 고정하고 Two-Pointer로 나머지 두 값을 찾는 방식.
• ✅ O(N²) 시간복잡도, O(1) 공간복잡도
• 정렬을 활용해 불필요한 계산을 줄이고, 효율적으로 중복 제거 가능
• 코드 예시:

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    let result: number[][] = [];
    
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 중복 제거
        
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right];
            
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while (left < right && nums[left] === nums[left - 1]) left++; // 중복 제거
                while (left < right && nums[right] === nums[right + 1]) right--; // 중복 제거
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

---

🔹 3. Two-Pointer 알고리즘이 유용한 문제 유형

Two-Pointer 알고리즘은 정렬된 배열에서 특정 조건을 만족하는 요소를 찾을 때 매우 유용합니다.

✅ 적용 가능한 문제 유형

1. 두 수의 합 문제 (2Sum 변형)
   • 예: 배열 내 두 숫자의 합이 특정 값(target)과 같은 경우 찾기
2. 세 수의 합 문제 (3Sum, 4Sum, N-Sum)
   • 예: 배열에서 3개의 숫자를 더해서 특정 값 만들기
3. 배열에서 특정 차이를 가지는 쌍 찾기
   • 예: 주어진 차이를 가지는 두 개의 숫자 찾기
4. 배열에서 가장 긴 연속 부분 문자열 찾기
   • 예: 정렬된 배열에서 특정 조건을 만족하는 부분 찾기
5. 투포인터를 활용한 투포인터-슬라이딩 윈도우
   • 예: 두 개의 포인터를 움직이며 최소 길이의 부분 배열 찾기

---

🔹 4. 결론

접근 방식	2Sum 시간복잡도	3Sum 시간복잡도	공간복잡도
Brute Force	O(N²)	O(N³)	O(1)
Hash Map 사용	O(N)	-	O(N)
Two-Pointer	O(N log N) (정렬) + O(N) = O(N)	O(N log N) (정렬) + O(N²) = O(N²)	O(1)

• 2Sum 문제는 HashMap을 활용하면 O(N) 최적화 가능.
• 3Sum 문제는 Two-Pointer를 활용하면 O(N²)로 줄일 수 있음.
• Two-Pointer는 정렬된 배열에서 특정 조합을 찾는 데 매우 유용.

코딩 테스트에서는 Brute Force를 먼저 떠올리고, 이후 최적화된 방법을 고민하는 연습이 필요합니다.

Two-Pointer는 코딩 테스트에서 자주 등장하는 핵심 기법이므로, 이를 활용하는 연습을 많이 해두는 것이 좋습니다! 🚀