C++로 해결하는 두 배 쌍 배열(Array of Doubled Pairs) 문제

문제 소개

길이가 짝수인 정수 배열 A가 있다고 가정해 봅시다. 이 배열을 임의로 재정렬했을 때, 모든 0 <= i < len(A)/2에 대해 A[2*i + 1] = 2 * A[2*i] 조건을 만족하도록 배치할 수 있는 경우에만 true를 반환해야 합니다.

예를 들어 입력이 [3,1,3,6]이라면 어떤 순서로 배치해도 조건을 충족할 수 없으므로 결과는 false입니다. 반면 [4,-2,2,-4]는 [-2,4,-4,2]처럼 재정렬하면 조건을 만족하므로 true를 반환합니다.

접근 방법

이 문제는 각 원소의 빈도수를 저장하는 맵(map)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 ‘어떤 값’과 ‘그 값의 두 배’가 하나의 쌍을 이루도록 개수를 차감해 나가는 것입니다.

알고리즘 단계

1. 맵 m을 생성하고, n := 배열 A의 크기로 설정한 뒤, A의 각 원소별 등장 횟수를 맵 m에 저장합니다.
2. cnt := A의 크기로 초기화합니다. (아직 쌍을 찾지 못한 원소의 개수)
3. 맵에 저장된 각 키-값 쌍(kv)에 대해 다음 과정을 반복합니다.
   • m[kv.key] > 0인 경우:
     • kv.key가 0이 아니면서 m[2 * kv.key] > 0이면:
       • x := min(m[kv.key], m[2 * kv.key])
       • cnt := cnt - (x * 2)
       • m[2 * kv.key] 값을 x만큼 감소
       • m[kv.key] 값을 x만큼 감소
     • kv.key가 0인 경우:
       • cnt := cnt - m[kv.key]
       • m[kv.key] := 0
4. 모든 반복이 끝난 뒤 cnt가 0이 아니면 false를, 0이면 true를 반환합니다.

여기서 0은 특별하게 처리해야 합니다. 2 * 0 = 0이므로 0은 자기 자신과 짝을 이루기 때문입니다. 또한 std::map은 키를 오름차순으로 순회하므로, 음수는 더 작은 값부터 양수 역시 더 작은 값부터 검사하게 됩니다. 덕분에 각 값이 자신의 두 배 값과 올바른 방향으로 매칭될 수 있습니다.

C++ 구현 예제

다음 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool canReorderDoubled(vector<int>& A) {
        map <int, int> m;
        int n = A.size();
        for(int i = 0; i < n; i++){
            m[A[i]]++;
        }
        int cnt = A.size();
        map <int, int> :: iterator it = m.begin();
        while(it != m.end()){
            if(m[it->first] > 0){
                if(it->first != 0 && m[it->first * 2] > 0){
                    int x = min(m[it->first], m[it->first * 2]);
                    cnt -= (x * 2);
                    m[it->first * 2] -= x;
                    m[it->first] -= x;
                }else if(it->first == 0){
                    cnt -= m[it->first];
                    m[it->first] = 0;
                }
            }
            it++;
        }
        return !cnt;
    }
};
main(){
    vector<int> v1 = {3,1,3,6};
    Solution ob;
    cout << (ob.canReorderDoubled(v1)) << endl;
    v1 = {4,-2,2,-4};
    cout << (ob.canReorderDoubled(v1));
}

입력

[3,1,3,6]
[4,-2,2,-4]

출력

0
1

첫 번째 입력 [3,1,3,6]은 조건을 만족하는 재정렬이 불가능하므로 0(false)이 출력되고, 두 번째 입력 [4,-2,2,-4]는 가능하므로 1(true)이 출력됩니다.