1. 454. 네 수의 합 II (4Sum II)

이 문제는 네 개의 배열에서 각각 하나씩 선택하여 합이 0이 되는 조합의 개수를 찾는 문제입니다. 해시맵을 사용하면 시간 복잡도를 O(n²)으로 줄일 수 있습니다. 먼저 첫 번째와 두 번째 배열의 모든 쌍의 합과 그 등장 횟수를 해시맵에 저장합니다. 그 다음 세 번째와 네 번째 배열의 모든 쌍의 합에 대해, 0에서 해당 합을 뺀 값이 해시맵에 존재하는지 확인하고 그 횟수를 결과에 더합니다.

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

public class FourSumCount {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int count = 0;
        Map<Integer, Integer> sumMap = new HashMap<>();
        for (int a : A) {
            for (int b : B) {
                int total = a + b;
                sumMap.put(total, sumMap.getOrDefault(total, 0) + 1);
            }
        }
        for (int c : C) {
            for (int d : D) {
                int target = -(c + d);
                count += sumMap.getOrDefault(target, 0);
            }
        }
        return count;
    }
}

2. 383. 랜섬 노트 (Ransom Note)

잡지(magazine)의 문자를 사용하여 랜섬 노트(ransomNote)를 만들 수 있는지 확인하는 문제입니다. 잡지 문자열의 각 문자 등장 횟수를 길이 26의 정수 배열에 기록합니다. 그 후 랜섬 노트의 각 문자에 대해 배열의 해당 위치 값을 감소시킵니다. 만약 배열에 음수 값이 하나라도 존재하면, 잡지에 없는 문자가 필요하다는 의미이므로 false를 반환합니다.

public class RansomNote {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) return false;
        int[] charCounts = new int[26];
        for (char c : magazine.toCharArray()) {
            charCounts[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            charCounts[c - 'a']--;
        }
        for (int count : charCounts) {
            if (count < 0) return false;
        }
        return true;
    }
}

3. 15. 세 수의 합 (3Sum)

정렬된 배열에서 세 수의 합이 0이 되는 모든 고유한 조합을 찾는 문제입니다. 첫 번째 포인터(i)는 배열을 순회하며 기준점을 잡고, 나머지 두 포인터(left, right)는 양 끝에서 시작하여 합을 조정합니다. 핵심은 중복된 조합을 피하기 위한 적절한 중복 제거입니다. 기준점 i의 중복은 이전 값과 비교하여 처리합니다. left와 right의 중복은 유효한 조합을 찾은 후에 처리하여, 동일한 값으로 인한 중복을 건너뜁니다. 정렬 후 첫 번째 값이 0보다 크면 더 이상 0을 만들 수 없으므로 반복을 종료합니다.

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

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

4. 18. 네 수의 합 (4Sum)

세 수의 합 문제를 확장한 것으로, 이번에는 네 수의 합이 특정 target 값이 되는 조합을 찾습니다. 첫 번째 포인터(k)와 두 번째 포인터(i)를 고정하고 나머지 두 포인터(left, right)로 합을 조정합니다. 가지치기(pruning)를 위해, 현재 합이 target을 초과하고 모든 숫자가 0 이상이면 더 이상 진행할 필요가 없습니다. 두 번째 포인터 i의 중복 제거 시, i는 항상 k+1보다 큰 위치에서만 확인합니다 (첫 번째 반복은 중복 제거 불필요). 합을 계산할 때는 정수 오버플로우를 방지하기 위해 long 타입으로 캐스팅합니다.

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

public class FourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int k = 0; k < nums.length; k++) {
            if (nums[k] > target && nums[k] >= 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            for (int i = k + 1; i < nums.length; i++) {
                if ((long) nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) break;
                if (i > k + 1 && nums[i] == nums[i - 1]) continue;
                int left = i + 1, right = nums.length - 1;
                while (left < right) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}