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

🚨 문제 파악

• 두 개의 큐 queue1, queue2가 주어짐
• 한 번에 한 원소를 한 큐의 앞에서 꺼내어 다른 큐 뒤에 넣는 작업 가능
• 이 과정을 반복하여 두 큐의 원소 합을 같게 만들고자 함
• 가능한 최소 작업 횟수를 구하라
• 불가능한 경우 -1을 반환

✅ 풀이 과정

1. 두 큐의 총합을 구한다

• sum1 = queue1의 총합
• sum2 = queue2의 총합
• 두 큐의 합이 같은지 비교하기 위해 필수

2. 합이 같은지 먼저 확인

• 만약 sum1 == sum2 → 이동 없이 바로 정답: 0
• 만약 (sum1 + sum2)가 홀수라면 → 애초에 같게 만들 수 없음 → -1 리턴

3. 두 큐를 각각 Queue 자료구조로 변환

• LinkedList 기반으로 구현
• 배열은 직접 앞에서 요소를 제거하는 데 비효율적이므로 Queue 사용

4. sum이 더 큰 쪽에서 작은 쪽으로 숫자를 하나씩 옮긴다

• sum1> sum2 → queue1에서 poll() → queue2에 add()
• sum2 > sum1 → 반대로 이동
• 이동 시마다 두 큐의 합도 갱신

5. 이동 횟수를 기록한다

• 한 번의 이동마다 count++
• 정답으로 반환할 값이 바로 이 count

6. 무한 루프 방지를 위해 이동 제한을 설정한다

• 최대 횟수는 queue1.length * 3 정도로 제한
• 이 이상이면 같은 숫자가 계속 순환 중이거나 해결 불가 상황이므로 → -1 반환

✨ 코드 구현

import java.util.*;

public class Solution {
    public int solution(int[] queue1, int[] queue2) {        
        int n = queue1.length;
        
        long sum1 = 0;
        long sum2 = 0;
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        for (int i = 0; i < n; i++) {
            q1.add(queue1[i]);
            q2.add(queue2[i]);
            sum1 += queue1[i];
            sum2 += queue2[i];
        }
        
        int count = 0;
        while (count <= n * 3) {
            if (sum1 == sum2) {
                return count;
            }
            
            if (sum1 > sum2) {
                int num = q1.poll();
                sum1 -= num;
                sum2 += num;
                q2.add(num);
            } else {
                int num = q2.poll();
                sum1 += num;
                sum2 -= num;
                q1.add(num);
            }
            count++;
        }
        return -1;
    }   
}