다수의 배열 조합 탐색 전략

여러 정수 배열에서 특정 조건을 만족하는 요소들의 조합 개수나 실제 조합 자체를 찾아야 할 때는 데이터 접근 속도와 중복 처리 방식을 적절히 선택해야 합니다. 해시 테이블을 이용한 빈도 집계와 정렬 기반 투 포인터 탐색은 모두 $O(N^2)$ 수준의 문제에서 성능을 결정하는 핵심 패턴입니다.

1. 쌍합 계산을 위한 해시 맵 활용 (4Sum II)

네 개의 배열로부터 각각 한 개씩 요소를 선택해 합이 $0$이 되는 케이스를 구할 때, 완전 탐색을 사용하면 $O(n^4)$의 시간 복잡도가 발생합니다. 대신 앞선 두 배열의 모든 가능한 합을 키로 두고 등장 횟수를 기록한 뒤, 뒷부분 두 배열의 합을 기반으로 목표값($Target Complement$)을 실시간 조회하면 조회 시간을 $O(1)$로 낮출 수 있습니다.

class Solution {
public:
    int fourSumCount(std::vector<int>& arrA, std::vector<int>& arrB, 
                     std::vector<int>& arrC, std::vector<int>& arrD) {
        std::unordered_map<int, int> pairFrequencies;
        
        for (const int& a : arrA) {
            for (const int& b : arrB) {
                pairFrequencies[a + b]++;
            }
        }

        int matchingCases = 0;
        for (const int& c : arrC) {
            for (const int& d : arrD) {
                int requiredPair = -(c + d);
                if (pairFrequencies.find(requiredPair) != pairFrequencies.end()) {
                    matchingCases += pairFrequencies[requiredPair];
                }
            }
        }
        return matchingCases;
    }
};

2. 문자 집합 검증용 고전 배열 (Ransom Note)

특정 문자열에 포함되어 있지 않은 글자가 요청되면 실패해야 하는 조건부 검증 문제입니다. 검색어영알파벳 소문자만 다루므로 해시맵 대신 크기 $26$의 고정 정수 배열을 사용하는 것이 메모리 할당 오버헤드를 제거하고 cache locality를 높입니다. 기준 문서를 스캔하며 카운터를 증가시키고, 요청문을 역순으로 채워나가며 음수가되는 순간 즉시 탈출하는 구조가 일반적입니다.

class Solution {
public:
    bool canConstruct(std::string requestStr, std::string sourceStr) {
        int letterIndices[26] = {0};
        
        for (char ch : sourceStr) {
            if (ch >= 'a' && ch <= 'z') {
                letterIndices[ch - 'a']++;
            }
        }
        
        for (char ch : requestStr) {
            if (ch >= 'a' && ch <= 'z') {
                int idx = ch - 'a';
                letterIndices[idx]--;
                if (letterIndices[idx] < 0) return false;
            }
        }
        return true;
    }
};

3. 정렬 및 양측 탐색을 통한 3Sum 최적화

세 수의 합이 $0$이 되는 고유한 triplet을 추출해야 합니다. 초기 접근법은 삼중 루프와 별도 컨테이너를 사용한 후처리로 인해 비효율적이었습니다. 배열을 선형시간 내에 정렬하고, 현재 고정값(`baseIdx`)을 기준으로 나머지 구간에서 좌우 양쪽 포인터(`searchLeft`, `searchRight`)를 좁혀가는 방식은 불필요한 비교를 대폭 줄입니다. 인접한 동일값을 미리 스킵하거나 추적 변수를 활용해 중복 삽입을 원천 차단합니다.

class Solution {
public:
    std::vector<std::vector<int>> threeSum(std::vector<int>& numbers) {
        std::vector<std::vector<int>> foundTriplets;
        std::sort(numbers.begin(), numbers.end());
        const int size = numbers.size();
        
        for (int baseIdx = 0; baseIdx < size - 2; ++baseIdx) {
            if (baseIdx > 0 && numbers[baseIdx] == numbers[baseIdx - 1]) continue;
            
            int searchLeft = baseIdx + 1;
            int searchRight = size - 1;
            
            while (searchLeft < searchRight) {
                int currentTotal = numbers[baseIdx] + numbers[searchLeft] + numbers[searchRight];
                
                if (currentTotal < 0) {
                    ++searchLeft;
                } else if (currentTotal > 0) {
                    --searchRight;
                } else {
                    foundTriplets.push_back({numbers[baseIdx], numbers[searchLeft], numbers[searchRight]});
                    
                    int leftVal = numbers[searchLeft];
                    int rightVal = numbers[searchRight];
                    
                    while (searchLeft < searchRight && numbers[searchLeft] == leftVal) ++searchLeft;
                    while (searchLeft < searchRight && numbers[searchRight] == rightVal) --searchRight;
                }
            }
        }
        return foundTriplets;
    }
};

4. 중첩 구조 확장 및 정수 오버플로 방어 (4Sum)

3Sum 알고리즘 프레임워크에 한 계층의 반복문을 추가하여 4변수 조건에 맞출 수 있습니다. 변수가 늘어나면서 중간 누적값이 $32$비트 정수 범위를 벗어날 수 있으므로, 명시적 타입 변환(`static_cast<long long>`)을 강제하여 런타임 오류를 방지해야 합니다. 조건 분기 논리는 동일하게 유지하되, 이중 루프에서도 이전 인덱스와 비교해 중복 시작점을 걸러내는 패턴을 적용합니다.

class Solution {
public:
    std::vector<std::vector<int>> fourSum(std::vector<int>& dataset, int targetValue) {
        std::vector<std::vector<int>> uniqueCombinations;
        std::sort(dataset.begin(), dataset.end());
        const int length = dataset.size();
        
        for (int i = 0; i < length - 3; ++i) {
            if (i > 0 && dataset[i] == dataset[i - 1]) continue;
            
            for (int j = i + 1; j < length - 2; ++j) {
                if (j > i + 1 && dataset[j] == dataset[j - 1]) continue;
                
                int ptrLow = j + 1;
                int ptrHigh = length - 1;
                
                while (ptrLow < ptrHigh) {
                    long long combinedSum = static_cast<long long>(dataset[i]) + 
                                            dataset[j] + dataset[ptrLow] + dataset[ptrHigh];
                    
                    if (combinedSum > targetValue) {
                        --ptrHigh;
                    } else if (combinedSum < targetValue) {
                        ++ptrLow;
                    } else {
                        uniqueCombinations.push_back({dataset[i], dataset[j], dataset[ptrLow], dataset[ptrHigh]});
                        
                        int lowSnapshot = dataset[ptrLow];
                        int highSnapshot = dataset[ptrHigh];
                        
                        while (ptrLow < ptrHigh && dataset[ptrLow] == lowSnapshot) ++ptrLow;
                        while (ptrLow < ptrHigh && dataset[ptrHigh] == highSnapshot) --ptrHigh;
                    }
                }
            }
        }
        return uniqueCombinations;
    }
};