2022 KAKAO TECH INTERNSHIP-두 큐 합 같게 만들기-C++

문제 바로가기

풀이법

1. 각 queue의 숫자합을 더한다.
2. 각 queue의 숫자를 비교해서 더 크면 빼서 다른 queue에 넣는다.
3. 어떤 방법으로도 같은 숫자를 만들수 없는 경우를 고려하여 queue의 size의 3배만큼 시도한 후에 못하면 return -1

1번

queue<int>q1;
    queue<int>q2;
    long long sum1=0;
    long long sum2=0;
    for(int i=0;i<queue1.size();i++){
        q1.push(queue1[i]);
        sum1+=queue1[i];
        q2.push(queue2[i]);
        sum2+=queue2[i];
    }

2번

long answer = 0;
    int flag = 0;
    long tmp = queue1.size() * 3;
    while(answer<=tmp){
        if(sum2>sum1){
            q1.push(q2.front());
            sum1+=q2.front();
            sum2-=q2.front();
            q2.pop();
        }else if(sum1>sum2){
            q2.push(q1.front());
            sum2+=q1.front();
            sum1-=q1.front();
            q1.pop();
        }else{
            flag=1;
            break;
        }
        answer++;
    }

sum1과 sum2를 비교해서 크면, pop하고 그 숫자를 다른 sum에다가 더해준다.

3번
위의 code에서 while문 조건에 해당하는 tmp가 queue.size의 3배이다.
3배 이내에 해결이 안되면 나가고,
만약 그전에 동일한 숫자가 있다면 else문을통해서 flag를 1로 세우고 나간다.

if(flag==1){
    return answer;
    }else{
        return -1;
    }

전체 코드

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

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