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

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

프로그래머스

 

 

문제 분석

이 문제는 두 큐의 원소 합을 동일하게 만드는 최소 작업 횟수를 구하는 문제입니다. 큐에서 원소를 추출하여 다른 큐에 삽입하는 과정을 반복하며, 이때 두 큐의 원소 합이 같아질 때까지의 최소 작업 횟수를 계산하는 것이 목표입니다.

문제 접근 과정

• 큐의 구조: 큐는 선입선출(FIFO) 구조로, 가장 먼저 삽입된 원소가 먼저 제거됩니다.
• 목표: 큐1과 큐2의 원소 합이 같아지도록 최소한의 작업을 수행해야 합니다. 각 작업은 큐에서 원소를 추출하고, 그 원소를 다른 큐에 삽입하는 과정을 포함합니다.
• 불가능한 경우: 두 큐의 총합이 홀수일 경우, 두 큐의 원소 합을 같게 만드는 것이 불가능하므로, 이때는 즉시 -1을 반환해야 합니다.
• 효율성: 큐의 길이가 최대 300,000이므로 시간 복잡도 O(n) 안에 문제를 해결해야 합니다. 따라서 효율적인 탐색 방법인 투 포인터(two-pointer) 기법을 사용합니다.

해결 알고리즘

• 큐의 합 계산: 두 큐의 원소를 모두 합쳐 하나의 배열로 만든 뒤, 두 큐의 합을 각각 계산합니다.
• 투 포인터 기법 사용: l과 r이라는 두 개의 포인터를 사용해, 각각 큐1과 큐2에서 원소를 빼거나 더하는 방식으로 큐의 합을 조정합니다.
• 큐의 합 조정:
  • 큐1의 합이 더 클 경우, 큐1에서 원소를 빼 큐2로 이동합니다.
  • 큐2의 합이 더 클 경우, 큐2에서 원소를 빼 큐1으로 이동합니다.
• 반복 조건: 큐의 합이 같아질 때까지 이 작업을 반복하며, 만약 두 큐의 합이 같아지지 않고 최대 한 바퀴 이상 돌았다면 불가능하므로 -1을 반환합니다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    
    // 두 큐를 이어 붙인 배열을 사용하여 pop 및 insert 처리를 쉽게 함
    vector<ll> mergedQueue;
    mergedQueue.reserve(queue1.size() + queue2.size()); // 메모리 할당 최적화
    mergedQueue.insert(mergedQueue.end(), queue1.begin(), queue1.end());
    mergedQueue.insert(mergedQueue.end(), queue2.begin(), queue2.end());

    int n = queue1.size();
    ll sum = 0; // 두 큐의 총합
    ll q1 = 0;  // 큐1의 합
    ll q2 = 0;  // 큐2의 합

    // 큐1과 큐2의 합을 구함
    for(int i = 0; i < n; i++){
        q1 += queue1[i];
        q2 += queue2[i];
        sum += queue1[i] + queue2[i];
    }
    
    // 전체 합이 홀수면 두 큐의 합을 같게 만드는 것이 불가능
    if(sum % 2 != 0) return -1;

    // 투 포인터 초기 설정
    int l = 0; // 큐1에서 idx
    int r = n; // 큐2에서 idx
    bool possible = false;

    // 두 큐의 합이 같아질 때까지 반복
    while(l <= r && r < mergedQueue.size()){
        if(q1 == q2) {
            possible = true;
            break;
        }
        if(q1 > q2){ // 큐1의 합이 크면 큐1에서 pop하여 큐2로 이동
            q1 -= mergedQueue[l];
            q2 += mergedQueue[l];
            l++;
            answer++;
        } else { // 큐2의 합이 크면 큐2에서 pop하여 큐1으로 이동
            q2 -= mergedQueue[r];
            q1 += mergedQueue[r];
            r++;
            answer++;
        }
    }

    return possible ? answer : -1; // 두 큐의 합이 같아진 경우 answer 반환, 불가능하면 -1 반환
}