Level 2. 두 큐 합 같게 만들기

Level 2. 두 큐 합 같게 만들기

 

 

우선 앞뒤에서 추가/삭제가 빈번하므로 vector 대신 deque로 변환해 사용했다.

• vector를 그대로 사용하고 인덱스로 관리해도 되긴 하다.

 

두 큐의 차이를 관리하면서 0이 되는 시점을 찾았다.

• 두 큐의 차가 홀수라면, 합을 같게 만들 수 없으므로 바로 종료한다.

 

첫 번째 큐에서 n1만큼 두 번째로 옮기고 두 번째 큐에서 n2만큼 첫 번째 큐로 옮기면, 두 큐가 바뀌었을 뿐 0으로 만들 수 없다는 의미이므로 종료한다.

• 그럼 while 문의 조건이 diff && (cnt1 != n1 || cnt2 != n2)이어야 하는데 코드와 같은 이유는 아래 설명한다.

 

큐에서 원소를 옮기는 작업이 합을 기준으로 하기 때문에, 개수 조건 경계에서 한 큐에서 연속해서 2번의 pop이 발생하면 조건에 영원히 걸리지 않아 무한 루프가 발생한다.

 

따라서 조건을 != 대신 <=로 바꾸고 개수 조건 경계를 2배로 해서, 한 큐의 모든 원소가 다른 큐로 넘어갈 정도로 수행해도 0으로 만들 수 없으면 무한 루프에 빠진 것으로 간주해 종료시킨다.

 

#include <iostream>
#include <vector>
#include <deque>
#include <numeric>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2)
{
    deque<int> deque1(queue1.begin(), queue1.end());
    deque<int> deque2(queue2.begin(), queue2.end());

    int cnt1 = 0, cnt2 = 0;
    int n1 = deque1.size() * 2, n2 = deque2.size() * 2;
    int diff = accumulate(deque1.begin(), deque1.end(), 0) - accumulate(deque2.begin(), deque2.end(), 0);

    if (diff & 1)
        return -1;

    while (diff && cnt1 <= n1 && cnt2 <= n2)
    {
        if (0 < diff)
        {
            deque2.emplace_back(deque1.front());
            deque1.pop_front();
            diff -= (deque2.back() * 2);
            ++cnt1;
        }
        else
        {
            deque1.emplace_back(deque2.front());
            deque2.pop_front();
            diff += (deque1.back() * 2);
            ++cnt2;
        }
    }

    return (diff == 0) ? (cnt1 + cnt2) : -1;
}