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

문제 URL

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

프로그래머스

이 문제는 길이가 같은 두 개의 큐가 주어졌을 때 각각의 두 큐에서 원소를 모두 합한 값이 서로 같아야 한다. 

합한 값이 더 큰 쪽의 큐를 pop 하여 다른 쪽의 큐로 넣어주는 방식을 반복하면서 문제를 해결하는데 이때, 반복문을 언제까지 돌아야 하는지 알아보자. 

 

한 큐에서 pop을 하다가 다시 자신의 기존 원소로 돌아오는 경우는 하나의 큐에서 (queue1 원소의 개수) + (queue2 원소의 개수) 만큼 pop을 진행했을 때이다. 따라서 하나의 큐를 두 벡터의 크기 합만큼 pop 했는데도 불구하고 조건을 만족하지 못한 경우에는 어떤 방법으로도 두 큐의 합을 같게 만들 수 없게 된다. 

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    long long sum = 0, sum2 = 0;
    queue<int> q, q2;

    /*
    for(int i=0; i<queue1_len; i++){
        sum += queue1[i];
        q.push(queue1[i]);
    }
    다음 구문 대신에 아래 구문을 사용
    */
    // 큐 안의 모든 원소의 합을 구함 
    for (int num : queue1) {
        sum += num;
        q.push(num);
    }
    for (int num : queue2) {
        sum2 += num;
        q2.push(num);
    }

    int idx = 0, idx2 = 0;
    int maxIdx = queue1.size() + queue2.size();  // 두 큐의 크기 합
    int answer = 0;  // 작업 횟수

    // 두 큐 중 하나라도 maxIdx를 넘으면 종료
    while (idx < maxIdx && idx2 < maxIdx) {
        if (sum == sum2) {
            return answer;
        }
    
        answer++;
        
        // 값이 큰 큐의 원소를 작은 큐로 보냄
        if (sum < sum2) {   
            int current = q2.front();
            q2.pop();

            q.push(current);
            sum += current;
            sum2 -= current;
            idx2++;
        }
        else {
            int current = q.front();
            q.pop();

            q2.push(current);
            sum2 += current;
            sum -= current;
            idx++;
        }
    }

    // 한 큐가 모든 원소를 돌 때까지 answer가 return 되지 않으면 -1을 return
    return -1;
}

참고: https://jaimemin.tistory.com/2180