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

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

프로그래머스

카카오 기출, 그리디 유형

 

sum1과 sum2를 구한 후 다음과 같이 그리디를 적용한다.

 

• sum1 > sum2인 경우, q1 pop후 q2로 insert
• sum1 < sum2인 경우, q2 pop 후 q1으로 insert

 

해당 방법이 왜 유요한지 검증해보자면, sum1과 sum2의 합이 같아야하므로 합이 큰 쪽에서 원소를 pop하여 작은 쪽으로 insert를 해줘야 최소 횟수로 두 합을 같게 만들 수 있기 때문이다.

 

추가로 주의할 점은 두 합을 같게 만들 수 없는 경우 예외처리를 하는 것인데, 단순히 '큐의 크기 * 2'만큼 시도를 해본 후 이때도 두 합이 같지 않으면 -1를 리턴하도록 처리를 하면 오답이 발생한다. 이는 하나의 큐가 모두 비워진 후 다시 해당 큐를 채우면서 탐색하는 경우가 있기 때문이다. 이런 경우 '큐의 크기 * 2' 범위가 넘어가므로, 넉넉하게 '* 3' 처리를 해주었다.

 

#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;

ll sum1, sum2;

int solution(vector<int> queue1, vector<int> queue2) {
    sum1 = accumulate(queue1.begin(), queue1.end(), 0);
    sum2 = accumulate(queue2.begin(), queue2.end(), 0);
    
    queue<int> q1, q2;
    for(int i = 0; i < queue1.size(); i++) {
        q1.push(queue1[i]);
        q2.push(queue2[i]);
    }
    
    int answer = 0;
    int n = 3 * queue1.size();
    while(1) {
        if(answer == n) return -1;
        if(sum1 == sum2) return answer;
        
        if(sum1 > sum2) {
            q2.push(q1.front());
            sum1 -= q1.front();
            sum2 += q1.front();
            q1.pop();
            answer++;
        } else if(sum1 < sum2) {
            q1.push(q2.front());
            sum2 -= q2.front();
            sum1 += q2.front();
            q2.pop();
            answer++;
        }
    }
}