lv2 / 두 큐 합 같게 만들기 / 카카오 / C++

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

---

일단, 문제에서 친절하게도 오버플로우의 가능성을 미리 말해줬기 때문에, 안전하게 long long 이상의 자료형을 사용하자. 필자는 uint64_t 자료형을 사용했다.

 

두 큐의 합이 같아지도록 큐의 FIFO특성을 이용하여 문제를 풀어야 한다. queue1, queue2의 원소의 총합을 sum1, sum2라고 한다면, 우리는 원소를 적절하게 push, pop하여 sum1 == sum2가 되도록 만들어야 한다. 이를 만족하려면 우리는 sum1과 sum2를 모두 (queue1과 queue2의 원소 총합) / 2가 되도록 원소를 이동해야한다. 이를 인지하고, 앞으로 들어오는 테스트케이스를 생각해보자.

 

1. 원소의 총합이 홀수인 경우.
2. 1에 포함되지 않는 일반적인 경우

1의 경우, 어떻게 해도 sum1 == sum2가 되지 않는다. 모든 원소는 자연수이고, (원소의 총합) / 2는 ~.5라는 값이 되어버리기 때문이다.

 

2의 경우가 우리가 생각해야하는 경우이다. 벡터의 원소의 합을 구하는 과정은 어쨌든 O(n)이기 때문에, 이를 반복해서는 안될 것 같았다. 따라서, 맨 처음에만 sum1, sum2를 구해주고, push, pop을 통해 원소가 없어지거나 생기는 경우, 이 원소의 값을 sum1, sum2에서 적절히 더하고 빼는 과정을 반복함으로써, 원하는 상황이 나올 때까지 반복한다.

 

그러면 우리는 한가지 더 의문을 가져야 한다. 얼마나 반복을 해야하는가? 무한반복을 돌리는 행위는 정말 위험하다. 당장 테스트케이스로 {1, 1}, {1, 5}가 들어온다면, 원소의 총합이 짝수이면서, 어떻게 해도 완성할 수 없다 (프로그래머스 예제 3이다). 이를 무한반복한다면... 결과는 안봐도 뻔하다.

 

이런 경우 우리는 최악의 경우를 생각해봐야 한다. 최악의 경우면 아마도 queue1과 queue2에서 원소를 하나씩만 남기고 모두 옮겨지는 경우일 것이다. 모두 바뀐다면 queue1과 queue2가 서로 뒤바뀐채 맨 처음과 같은 상황일테니까. 그렇다는 것은 대략 queue1(또는 queue2)의 길이의 2배만큼의 반복을 해야한다. 왜 길이만큼이 아니냐고? 하나의 원소가 push, pop되고, queue1과 queue2의 원소 한개를 제외한 모든 원소에서 이 작업을 행하기 때문에 대략 길이의 2배만큼 진행해야한다. 하지만 혹시 모르는 상황을 대비하기 위해 넉넉하게 길이의 3배로 잡았다.

 

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;
using ull = uint64_t;

int solution(vector<int> queue1, vector<int> queue2) {
    ull sum1 = accumulate(ALL(queue1), 0);
    ull sum2 = accumulate(ALL(queue2), 0);
    ull total = sum1 + sum2;
    if (total & 1) return -1; // 홀수면 어짜피 안된다. 그냥 거른다.
    
    int answer = 0;
    int len = queue1.size();
    int temp;
    deque<int> q1, q2;

    while(!queue1.empty()) {
        q1.push_front(queue1.back());
        queue1.pop_back();
    }
    while(!queue2.empty()) {
        q2.push_front(queue2.back());
        queue2.pop_back();
    }
    for(int i = 0; i < 3 * len; i++) {
        if (sum1 > sum2) {
            sum1 -= q1.front();
            sum2 += q1.front();
            temp = q1.front();
            q1.pop_front();
            q2.push_back(temp);
            answer++;
        }
        else if (sum1 < sum2) {
            sum1 += q2.front();
            sum2 -= q2.front();
            temp = q2.front();
            q1.push_back(temp);
            q2.pop_front();
            answer++;
        }
        else { // 합이 같은 경우. 끝
            return answer;
        }
    }
    return -1; // 원소 총합이 짝수이고, 어떤 경우로도 합을 같게 할 수 없는 경우.
}