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

---

🔗 문제 링크

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

프로그래머스

---

728x90

반응형

👩‍💻 코드

#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <iostream>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    int n = queue1.size();
    long long sum1 = accumulate(queue1.begin(), queue1.end(), 0LL);
    long long sum2 = accumulate(queue2.begin(), queue2.end(), 0LL);
    long long target = (sum1 + sum2) / 2;
    queue<int> q1;
    queue<int> q2;
    
    if ((sum1 + sum2) % 2 != 0) {
        return -1;
    }
    
    for(int i=0; i<n; i++){
        q1.push(queue1[i]);
        q2.push(queue2[i]);
    }

    while (answer <= 4 * n) {
        if (sum1 == target) {
            return answer;
        }

        if (sum1 < target) {
            if (q2.empty()) {
                break;
            }

            int value = q2.front();
            q2.pop();
            q1.push(value);
            sum1 += value;
            sum2 -= value;
        } else {
            if (q1.empty()) {
                break;
            }

            int value = q1.front();
            q1.pop();
            q2.push(value);
            sum1 -= value;
            sum2 += value;
        }

        answer++;
    }

    return -1;
}

---

📝 풀이

queue1의 합과 queue2의 합을 더하여 반을 나눈 값을 목표로 설정합니다.

이 때 두 큐의 합이 홀수라면 반으로 나눌 수 없으니 -1을 return 합니다.

 

문제에 주어진 vector<int>를 queue<int>에 저장합니다.

sum1과 target을 비교하여 sum1이 클 경우 q1에서 pop하여 q2에 push합니다.

sum1이 작을 경우 q2에서 pop하여 q1에 push합니다.

이 과정을 sum1과 target이 같아질 때까지 반복합니다.

sum1과 target이 같아진다면 answer을 return 합니다.