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

문제 링크

---

1. 아이디어

두 큐의 합을 같게 만드는 문제로, queue1의 합이 더 크면 queue1의 앞 원소를 queue2의 뒤로, queue2의 합이 더 크면 queue2의 앞 원소를 queue1의 뒤로 옮기는 과정을 반복하면 된다. 어느 쪽을 옮길지가 매 순간 하나로 정해지므로 탐색이 아니라 단순 반복으로 처리할 수 있다. 이를 효율적으로 수행하기 위해 주어진 배열을 큐에 담아 처리했고, 합을 매번 순회해서 구하는 대신 미리 구해둔 뒤 원소 이동 시 함께 갱신해줬다.

다만 두 큐는 합이 같아질 수 없는 경우도 있으므로, 원소를 이동하는 횟수에 상한을 두고 그 안에서 합이 같아지는 순간을 찾지 못하면 -1을 반환하도록 했다. 상한은 두 큐의 길이 합의 두 배로 잡아줬다.

---

2. 복잡도

시간복잡도	공간복잡도
$O(N)$	$O(N)$

$N$ = queue1 길이(= queue2 길이)

---

3. 코드

풀이 [Java][C++]

import java.util.*;

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

        long sum1 = 0;
        long sum2 = 0;

        for (int x : queue1) {
            q1.offer(x);
            sum1 += x;
        }
        for (int x : queue2) {
            q2.offer(x);
            sum2 += x;
        }

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

        return -1;
    }
}

#include <queue>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    queue<int> q1;
    queue<int> q2;

    long long sum1 = 0;
    long long sum2 = 0;

    for (int x : queue1) {
        q1.push(x);
        sum1 += x;
    }
    for (int x : queue2) {
        q2.push(x);
        sum2 += x;
    }

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

    return -1;
}

---

4. 리뷰

이동 횟수 상한을 두 큐 길이 합의 두 배로 잡으면 됐는데 엄밀하게 이게 최적인지 증명하기는 어려웠다.

---