[ 프로그래머스 ] 두 큐 합 같게 만들기

문제

---

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

풀이

---

큐의 특성을 활용하여 주어진 각 큐의 원소 합이 같게 만드는 문제이다. 원소 합이 같게하기 위해 더 높은 원소 합을 가진 큐가 다른 큐에게 원소를 전달하는 것을 반복하여 문제를 푼다. 다만 가장 큰 원소와 다른 모든 원소를 합쳐도 원소 합을 같게 만들 수 없거나, 일정 이상의 순회를 거치면 -1을 return하도록 한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) 
{
    long long answer = 0;
    long long q1Sum = 0;
    long long q2Sum = 0;
    //큐 하나에서만 빼서 가능하면 그렇게 하기
    
    queue<long long> q1, q2;

    for (long long i = 0; i < queue1.size(); i++)
    {
        q1.push(queue1[i]);
        q2.push(queue2[i]);

        q1Sum += queue1[i];
        q2Sum += queue2[i];
    }

    long long target_sum = (q1Sum + q2Sum) / 2;
    
    //가장 큰 원소와 다른 모든 원소를 합쳐도 안될때도 추가해야함
    if ((q1Sum == target_sum && q2Sum != target_sum) ||(q1Sum != target_sum && q2Sum == target_sum))
    {
        answer = -1;
    }

    else
    {
        long long max = queue1.size() * 4;

        while(!(q1Sum == q2Sum))
        {
            if (q1Sum < q2Sum)
            {
                q1.push(q2.front());
                q1Sum += q2.front();
                q2Sum -= q2.front();
                q2.pop();
                answer++;
            }

            else
            {
                q2.push(q1.front());
                q2Sum += q1.front();
                q1Sum -= q1.front();
                q1.pop();
                answer++;
            }

            if (answer >= max)
            {
                answer = -1;
                break;
            }
        }

    }


    return answer;
}