[Programmers/Java] 두 큐 합 같게 만들기

[Programmers/Java] 두 큐 합 같게 만들기

프로그래머스

---

문제 해석

이 문제는 두 개의 큐의 원소 합을 동일하게 만들기 위해 필요한 최소한의 원소 이동 횟수를 계산하는 것이다. 각 큐에서 원소를 추출하고 다른 큐에 추가하는 방식으로 큐의 합을 조정할 수 있다. 주어진 조건은 두 큐의 길이가 동일하며, 모든 원소의 총합을 2로 나눈 값이 각 큐의 목표 합이 되어야 한다. 만약 두 큐의 원소 합을 같게 만들 수 없는 경우, -1을 반환해야 한다.

풀이 과정

해당 코드는 두 큐의 원소 합이 같아질 때까지 원소를 이동시키는 과정을 구현한다. 각 큐의 원소들을 ArrayDeque를 사용해 관리하고, 원소들의 총합을 long 타입 변수로 관리하여 오버플로우를 방지한다. 이동이 필요한 경우, 한 큐의 합이 다른 큐의 합보다 크면, 큰 큐에서 원소를 추출하여 작은 큐에 추가한다. 이 과정을 반복하여 두 큐의 합이 동일해지면 이동 횟수를 반환하고, 모든 가능한 조작을 수행한 후에도 합이 같지 않으면 -1을 반환한다.

코드

package edu.ssafy.im.PRO.No118667;

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -1;

        long s1 = 0, s2 = 0;
        Queue<Integer> q1 = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();

        // 큐 초기화 및 합계 계산
        for (int q : queue1) {
            q1.offer(q);
            s1 += q;
        }

        for (int q : queue2) {
            q2.offer(q);
            s2 += q;
        }

        int cnt = 0;
        // 큐의 원소를 이동시키며 합을 맞추는 과정
        while (cnt <= queue1.length * 4) {
            if (s1 > s2) {
                int q = q1.poll();
                q2.offer(q);
                s1 -= q;
                s2 += q;
            } else if (s1 < s2) {
                int q = q2.poll();
                q1.offer(q);
                s1 += q;
                s2 -= q;
            } else if (s1 == s2) {
                return cnt;
            }
            cnt++;
        }

        return answer;
    }
}

시간 복잡도 분석

이 알고리즘은 최대 𝑛×4번의 조작을 시도하며, 여기서 𝑛은 큐의 길이이다. 각 조작은 큐에서의 추출 및 삽입으로, 𝑂(1)의 시간 복잡도를 가진다. 따라서 전체 시간 복잡도는 𝑂(𝑛)이 된다.

느낀점

이 문제를 통해 큐를 사용한 동적 데이터 처리와 문제 해결 과정에서의 효율적인 접근 방법에 대해 학습할 수 있었다. 또한, 문제의 조건을 정확히 파악하고 이를 코드로 구현하는 능력이 중요함을 다시 한번 깨닫게 되었다.