[programmers] 두 큐 합 같게 만들기

문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

 

제한사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

풀이

입력이 vector 로 주어지는데 이를 큐로 변환해주고 합이 큰 queue에서 작은 queue로 옮겨준다. 

개념은 쉬운데 최대 반복을 몇번 돌릴지가 문제이다. 

한 queue 원래 상태로 돌아오려면 총 4n 만큼 움직여야해서 (길이가 긴 queue.size) * 4로 제한을 뒀다. (맞는지는 모르겠다..)

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = -1;
    long long queue1_sum = 0, queue2_sum = 0;
    queue<int> q1, q2;
    
    for(auto num : queue1){
        queue1_sum += num;
        q1.push(num);
    }
    for(auto num : queue2){
        queue2_sum += num;
        q2.push(num);
    }
    if((queue1_sum % 2 + queue2_sum % 2) % 2 != 0)return -1;
    int cnt = 0, idx1 = 0, idx2 = 0;
    int maxcnt = queue1.size() > queue2.size() ? queue1.size()*4 : queue2.size()*4;
    while(queue1_sum != queue2_sum && (idx1 < maxcnt && idx2 < maxcnt)){
        
        if(queue1_sum > queue2_sum){
            int temp = q1.front();
            q1.pop();
            queue1_sum -= temp;
            queue2_sum += temp;
            q2.push(temp);
            idx1++;
        }else{
            int temp = q2.front();
            q2.pop();
            queue2_sum -= temp;
            queue1_sum += temp;
            q1.push(temp);
            idx2++;
        }
        cnt++;
    }
    
    answer = queue1_sum == queue2_sum ? cnt : -1;
    return answer;
}