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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

queue1과 queue2가 주어졌을 때, 각 원소의 합을 같게 만들기 위한 최소 이동(pop+insert) 횟수를 구하는 문제이다.

 

그리디적으로 생각해보면, queue1의 현재 원소합이 sum1이고 queue2의 현재 원소합이 sum2 일 때, 

1) sum1 > sum2 이면 queue1의 원소를 queue2로 이동시키는 것이 유리하다.

2) sum1 < sum2 이면 queue2 원소를 queue1으로 이동시키는 것이 유리하다.

 

따라서, 반복적으로 두 큐의 원소 합을 비교하여 이를 같게 만드는데 유리한 방향으로 원소를 이동시켜나가면 된다.

이 때, 특정 횟수 이상으로 이동이 길어지면 두 큐의 합을 같게 만드는 것이 불가능하다는 이야기 이므로 반복문을 빠져나와 -1을 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int solution(vector<int> queue1, vector<int> queue2) {
    
    queue<int> q1, q2;
    long long sum1 = 0, sum2 = 0;
    int cnt = 0;
    
    for (auto x : queue1) {
        q1.push(x);
        sum1 += x;
    }
    
    for (auto x : queue2) {
        q2.push(x);
        sum2 += x;
    }
    
    while (true) {
        if (cnt > queue1.size()*3) break;
        if (sum1 == sum2) return cnt;
        else if (sum1 > sum2) {
            sum1 -= q1.front();
            sum2 += q1.front();
            q2.push(q1.front());
            q1.pop();
            cnt++;
        }
        else {
            sum1 += q2.front();
            sum2 -= q2.front();
            q1.push(q2.front());
            q2.pop();
            cnt++;
        }
    }
    return -1;
}