프로그래머스 - 두 큐 합 같게 만들기 [2022 KAKAO TECH INTERNSHIP]

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=cpp

프로그래머스

 

처음 문제를 접했을 때 "최소비용", "최소거리" 등이 보이면 가장 먼저 생각나는 건 BFS, 다익스트라 등이다.

 

그래서 그렇게 생각했는데 방문체크를 할 수가 없었다.

 

그리고 이 문제의 의도는 Greedy 알고리즘이다. 두 합이 같아져야 하므로 언제나 큰 쪽에서 작은 쪽으로 pop하여 푸쉬하는 것이다.

 

그리고 최대까지 모두 돌았는데도 정답이 아니라면 이것은 방법이 없는 것으로 간주한다. 

 

개인적으로 대충 1만정도 질렀는데 맞았다. 하지만 수학적으로 생각하면 queue1 에서 2까지 모두 옮기고 다시 모두 옮기는 것이므로, 2 * N + N = 3 * N 이다.

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#define ll long long
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    ll sum1 = 0, sum2 = 0;
    
    queue<int> q1, q2;
    
    for(int a : queue1) {
        sum1 += a;
        q1.push(a);
    }
    for(int a : queue2) {
        sum2 += a;
        q2.push(a);
    }
    
    if(sum1 + sum2 % 2 == 1) return -1;
    
    while(sum1 != sum2){
        if(sum1 > sum2){
            sum1 -= q1.front();
            sum2 += q1.front();
            q2.push(q1.front());
            q1.pop();
        }else if(sum1 < sum2){
            sum2 -= q2.front();
            sum1 += q2.front();
            q1.push(q2.front());
            q2.pop();
        }
        answer++;
        
        if(answer == 10000000) break;
    }
    
    if(answer == 10000000) return -1;
    else return answer;
}