454. 네 수의 합 (두 쌍으로 분할)

문제는 네 개의 배열에서 각각 하나씩 원소를 선택하여 합이 0이 되는 조합의 수를 세는 것이다. 접근 방식은 두 배열을 먼저 조합해 합을 해시맵에 저장하고, 나머지 두 배열의 합과 보완되는 값을 탐색하는 방식이다.

• 첫 번째 단계: nums1과 nums2의 모든 쌍의 합을 계산하여 Map<합, 등장 횟수>로 저장한다.
• 두 번째 단계: nums3와 nums4의 각 쌍의 합을 구하고, 그 음수 값이 맵에 존재하는지 확인한다. 존재하면 해당 횟수만큼 결과에 더한다.

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> sumMap = new HashMap<>();
        
        // nums1과 nums2의 모든 조합의 합을 기록
        for (int a : nums1) {
            for (int b : nums2) {
                int total = a + b;
                sumMap.put(total, sumMap.getOrDefault(total, 0) + 1);
            }
        }

        int count = 0;
        // nums3과 nums4의 조합과 보완값 검색
        for (int c : nums3) {
            for (int d : nums4) {
                int complement = -(c + d);
                if (sumMap.containsKey(complement)) {
                    count += sumMap.get(complement);
                }
            }
        }

        return count;
    }
}

383. 랜섬 메시지 생성 가능성 판단

주어진 magazine 문자열에서 ransomNote 문자열의 모든 문자를 구성할 수 있는지를 확인하는 문제다. 이는 문자 빈도 비교를 통해 해결 가능하다.

• 기본 아이디어: magazine의 각 문자 빈도를 카운트한 후, ransomNote에서 사용된 문자가 충분한지 검사.
• 빈도 감소 과정에서 부족한 경우 바로 false 반환.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charCount = new int[26];
        
        // magazine의 문자 빈도 기록
        for (char c : magazine.toCharArray()) {
            charCount[c - 'a']++;
        }

        // ransomNote의 문자를 차감하며 확인
        for (char c : ransomNote.toCharArray()) {
            int idx = c - 'a';
            if (charCount[idx] == 0) return false;
            charCount[idx]--;
        }

        return true;
    }
}

15. 세 수의 합 (정렬 + 양방향 포인터)

배열에서 합이 0인 세 정수의 조합을 찾는 문제. 중복 제거와 효율적인 탐색이 핵심이다.

• 정렬 후 첫 번째 요소를 고정하고, 나머지 두 요소는 양끝 포인터로 탐색.
• 중복 제거: 현재 요소가 이전과 동일하면 건너뛰며, 발견한 조합 이후에도 동일한 값이 반복되면 계속 건너뛴다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break; // 첫 번째 요소가 양수면 더 이상 불가능
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    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--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }
}

18. 네 수의 합 (보조 조건 포함)

세 수의 합 문제의 확장판. 목표 합이 0이 아닌 임의의 값일 수 있으며, 이에 따라 가지치기 전략이 달라진다.

• 정렬 후 두 개의 외부 루프로 첫 두 요소를 고정하고, 나머지 두 요소는 양끝 포인터로 탐색.
• 최적화: 첫 번째 요소가 양수이고, 전체 합이 이미 목표보다 크다면 종료.
• 중복 처리는 각 루프 내에서 이전 값과 비교하여 수행.

class Solution {
    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 - 3; k++) {
            if (k > 0 && nums[k] == nums[k-1]) continue;
            if (nums[k] > 0 && nums[k] > target) break; // 가지치기

            for (int i = k + 1; i < nums.length - 2; i++) {
                if (i > k + 1 && nums[i] == nums[i-1]) continue;

                int left = i + 1;
                int right = nums.length - 1;

                while (left < right) {
                    long sum = (long)nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[k], 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--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return result;
    }
}