[프로그래머스][level2] 두 큐 합 같게 만들기 (C++)

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

프로그래머스

 

 

[난이도] level2
[유형] 구현

[풀이]
전체 합의 절반 값이 t일 때, queue1의 값을 t로 만들면 됩니다.
실제로 큐 두개를 선언하여 queue1,queue2에 넣고 현재 queue1 값들의 합을 sum이라고 했을 때,
sum의 값이 t보다 크면 queue1 에서 pop, t보다 작으면 queue2에서 pop 하는 방식으로 sum이 t가 될때까지 진행해줍니다.
최대 연산 횟수는 queue1,queue2의 초기 사이즈를 N이라고 했을 때,
queue1의 값을 모두 queue2로 옮겼다가 queue2에 있는 값을 다시 queue1으로 옮기는 경우 이므로 N+2*N = 3*N 이 됩니다.
연산 과정에서 무한히 반복될 수 있으므로 최대 3*N만큼만 루프를 돌려줍니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
ll sum,sum2;
queue<int> q1,q2;
int N;
int solution(vector<int> a, vector<int> b) {
    for(int i=0;i<a.size();i++){
        sum+=a[i];
        sum2+=b[i];
        q1.push(a[i]);
        q2.push(b[i]);
    }

    if((sum+sum2)%2)return -1;
    ll t = (sum+sum2)/2;

    int i=0,j=0,ans=0,n=a.size()*3;
    while(n--){
        if(sum>t){
            ans++;
            int v = q1.front();
            sum-=v;
            q2.push(v);
            q1.pop();
        }else if(sum<t){
            ans++; 
            int v = q2.front();
            sum+=v;
            q1.push(v);
            q2.pop();            
        }else{
            return ans;
        }
    }
    return -1;
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/두_큐_합_같게_만들기.cpp