[프로그래머스] 두 큐 합 같게 만들기 풀이 및 코드 분석

문제 링크

---

1. 문제 분석

두 개의 큐가 주어지고, 한 큐에서 원소를 빼서 다른 큐에 추가하는 방식으로 두 큐의 원소 합을 같게 만들고자 한다. 최소 작업 횟수를 구하는 것이 목표이며, 어떤 방법으로도 같게 만들 수 없다면 -1을 반환해야 한다.

핵심 포인트

1. 총합이 홀수이면 불가능
   • 두 큐의 원소 합이 홀수이면 절대 같은 값으로 만들 수 없다.
2. 투 포인터 (Two Pointers) 활용
   • 큐의 원소를 이동하며 합을 맞추는 방식이므로, 투 포인터 또는 슬라이딩 윈도우 기법을 활용할 수 있다.
3. 최대 이동 횟수 제한
   • 한 큐의 길이가 n일 때, 최악의 경우 3 * n번의 이동 내에서 해결할 수 있어야 한다.

---

2. 해결 방법

1. 초기 설정
   • 두 큐의 합을 각각 계산한다.
   • sum1, sum2의 합이 홀수이면 -1 반환.
   • 두 큐를 LinkedList(큐)로 변환하여 사용한다.
2. 투 포인터 (슬라이딩 윈도우) 방식 적용
   • sum1이 sum2보다 크면 queue1에서 pop한 후 queue2에 삽입.
   • sum2이 sum1보다 크면 queue2에서 pop한 후 queue1에 삽입.
   • 두 큐의 합이 같아지면 반복 종료.
   • 최대 3 * n번의 연산을 초과하면 -1 반환.

---

3. 코드 구현

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        long sum1 = 0, sum2 = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        // 초기 합 계산 및 큐에 삽입
        for (int i = 0; i < queue1.length; i++) {
            sum1 += queue1[i];
            sum2 += queue2[i];
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }

        // 총합이 홀수이면 불가능
        if ((sum1 + sum2) % 2 != 0) return -1;

        long target = (sum1 + sum2) / 2;
        int cnt = 0, limit = queue1.length * 3; // 최대 이동 가능 횟수 제한

        while (cnt < limit) {
            if (sum1 == target) return cnt; // 종료 조건

            if (sum1 > target) { // q1에서 pop 후 q2에 삽입
                int num = q1.poll();
                sum1 -= num;
                sum2 += num;
                q2.add(num);
            } else { // q2에서 pop 후 q1에 삽입
                int num = q2.poll();
                sum2 -= num;
                sum1 += num;
                q1.add(num);
            }
            cnt++;
        }

        return -1; // 불가능한 경우
    }
}

---

4. 코드 분석

1. 입력 처리 및 초기화

long sum1 = 0, sum2 = 0;
Queue<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();

for (int i = 0; i < queue1.length; i++) {
    sum1 += queue1[i];
    sum2 += queue2[i];
    q1.add(queue1[i]);
    q2.add(queue2[i]);
}

• 두 큐의 합을 sum1, sum2에 저장.
• queue1과 queue2를 LinkedList 큐로 변환.

---

2. 불가능한 경우 확인

if ((sum1 + sum2) % 2 != 0) return -1;

• 전체 합이 홀수이면 두 큐의 합이 같아질 수 없으므로 -1 반환.

---

3. 투 포인터 방식 적용

long target = (sum1 + sum2) / 2;
int cnt = 0, limit = queue1.length * 3;

while (cnt < limit) {
    if (sum1 == target) return cnt; // 목표 달성 시 종료

    if (sum1 > target) { // sum1이 크면 q1에서 pop 후 q2에 삽입
        int num = q1.poll();
        sum1 -= num;
        sum2 += num;
        q2.add(num);
    } else { // sum2가 크면 q2에서 pop 후 q1에 삽입
        int num = q2.poll();
        sum2 -= num;
        sum1 += num;
        q1.add(num);
    }
    cnt++;
}

• sum1 > target이면 queue1에서 pop하여 queue2에 삽입.
• sum2 > target이면 queue2에서 pop하여 queue1에 삽입.
• cnt가 3 * n을 초과하면 -1 반환.

---

5. 개선할 점 및 대체 방법

1. Deque 사용
   • LinkedList보다 ArrayDeque이 poll() 연산에서 더 빠르므로 변경 가능.
2. 배열을 사용한 포인터 접근 방식
   • 큐를 두 개의 포인터로 관리하여 poll()을 없애고 start 인덱스를 조정하는 방식 사용 가능.
3. 특정 값이 너무 커서 해결이 불가능한 경우 미리 검사
   • 두 큐의 최대값이 목표 값보다 크면 -1을 즉시 반환할 수 있다.