[Programmers] 118667번 - 두 큐 합 같게 만들기 [Java][C++]

문제 링크

---

1. 문제 풀이

두 큐에서 각 큐의 원소의 합이 서로 같아지는지 찾는 문제로 각 큐의 합을 미리 구한 후 합이 큰 큐에서 합이 작은 큐로 원소를 이동하는 과정을 반복하면 된다. 이때 각 큐의 원소 합을 같게 만들 수 없는지를 판단해야하는데 이는 큐의 특정 원소가 다른 큐에 들어갔다가 다시 원래 큐로 돌아로는 것을 모든 원소에 대해 만족하는, 즉 두 큐의 원소 수의 합의 두 배만큼만 반복해보면 알 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> q1 = arrToQueue(queue1);
        Queue<Integer> q2 = arrToQueue(queue2);

        long sum1 = addition(queue1);
        long sum2 = addition(queue2);

        int cnt = 0;
        int max = (q1.size() + q2.size()) * 2;

        while (cnt < max) {
            if (sum1 < sum2) {
                sum1 += q2.peek();
                sum2 -= q2.peek();
                q1.offer(q2.poll());
            } else if (sum1 > sum2) {
                sum1 -= q1.peek();
                sum2 += q1.peek();
                q2.offer(q1.poll());
            } else {
                return cnt;
            }

            cnt++;
        }

        return -1;
    }

    static Queue<Integer> arrToQueue(int[] arr) {
        Queue<Integer> q = new ArrayDeque<>();

        for (int n : arr) {
            q.offer(n);
        }

        return q;
    }

    static long addition(int[] arr) {
        long sum = 0;

        for (int n : arr) {
            sum += n;
        }

        return sum;
    }
}

2. 풀이 [C++]

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

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    queue<int> q1;
    queue<int> q2;
    for (int x : queue1) q1.push(x);
    for (int x : queue2) q2.push(x);

    long long sum1 = 0;
    long long sum2 = 0;
    for (int x : queue1) sum1 += x;
    for (int x : queue2) sum2 += x;

    int cnt = 0;
    int mx = (q1.size() + q2.size()) * 2;

    while (cnt < mx) {
        if (sum1 < sum2) {
            sum1 += q2.front();
            sum2 -= q2.front();
            q1.push(q2.front());
            q2.pop();
        } else if (sum1 > sum2) {
            sum1 -= q1.front();
            sum2 += q1.front();
            q2.push(q1.front());
            q1.pop();
        } else {
            return cnt;
        }

        cnt++;
    }

    return -1;
}

---