두 큐 합 같게 만들기

2026.07.02

문제 풀이

1차 실행 오류

---

86.7/100
int 사용으로 인한 오버플로우 발생

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Deque<Integer> q1 = new ArrayDeque<>();
        Deque<Integer> q2 = new ArrayDeque<>();
        int len = queue1.length;
        int total = 0;
        int totalQ1 = 0;
        int totalQ2 = 0;
        
        for (int i = 0; i < len; i++) {
            int n = queue1[i];
            q1.offer(n);
            total += n;
            totalQ1 += n;
        }
        for (int i = 0; i < len; i++) {
            int n = queue2[i];
            q2.offer(n);
            total += n;
            totalQ2 += n;
        }
        
        if (total % 2 != 0) {
            return -1;
        }
        if (totalQ1 == totalQ2) {
            return 0;
        }
        int count = 0;
        while(true) {
            if (totalQ1 == totalQ2) {
                break;
            }
            if (totalQ1 > totalQ2) {
                Integer n = q1.poll();
                q2.offer(n);
                if (n == null) {
                    return -1;
                }
                totalQ1 -= n;
                totalQ2 += n;
                count++;
            }
            else {
                Integer n = q2.poll();
                q1.offer(n);
                if (n == null) {
                    return -1;
                }
                totalQ1 += n;
                totalQ2 -= n;
                count++;
            }
            if (count >= len * 2) {
                return -1;
            }
        }
        
        return count;
    }
}

2차 실행 오류

---

96.7/100

if (count >= len * 2) {
	return -1;
}

코드를 훑어보며 예외적인 상황은 전부 다 해결했고,
남은 부분은 루프를 계속해서 돌게 되면 반복적으로 순회하게 되므로
임의로 정해둔 count의 범위가 너무 좁은 것이 문제였음

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public long solution(int[] queue1, int[] queue2) {
        Deque<Long> q1 = new ArrayDeque<>();
        Deque<Long> q2 = new ArrayDeque<>();
        long len = queue1.length;
        long total = 0;
        long totalQ1 = 0;
        long totalQ2 = 0;
        
        for (int i = 0; i < len; i++) {
            long n = queue1[i];
            q1.offer(n);
            total += n;
            totalQ1 += n;
        }
        for (int i = 0; i < len; i++) {
            long n = queue2[i];
            q2.offer(n);
            total += n;
            totalQ2 += n;
        }
        
        if (total % 2 != 0) {
            return -1;
        }
        if (totalQ1 == totalQ2) {
            return 0;
        }
        long count = 0;
        while(true) {
            if (totalQ1 == totalQ2) {
                break;
            }
            if (totalQ1 > totalQ2) {
                Long n = q1.poll();
                q2.offer(n);
                if (n == null) {
                    return -1;
                }
                totalQ1 -= n;
                totalQ2 += n;
                count++;
            }
            else {
                Long n = q2.poll();
                q1.offer(n);
                if (n == null) {
                    return -1;
                }
                totalQ1 += n;
                totalQ2 -= n;
                count++;
            }
            if (count >= len * 2) {
                return -1;
            }
        }
        
        return count;
    }
}

나의 코드

소요 시간: 1시간 9분

시간 복잡도: $O(n)$

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public long solution(int[] queue1, int[] queue2) {
        Deque<Long> q1 = new ArrayDeque<>();
        Deque<Long> q2 = new ArrayDeque<>();
        long len = queue1.length;
        long totalQ1 = 0;
        long totalQ2 = 0;
        long count = 0;
        
        for (int i = 0; i < len; i++) {
            long n = queue1[i];
            q1.offer(n);
            totalQ1 += n;
        }
        for (int i = 0; i < len; i++) {
            long n = queue2[i];
            q2.offer(n);
            totalQ2 += n;
        }
        
        if ((totalQ1 + totalQ2) % 2 != 0) { // 두 큐의 원소의 합이 홀수일 때
            return -1;
        }
        if (totalQ1 == totalQ2) { // 이미 두 큐의 합이 같을 때
            return count;
        }
        
        while(true) {
            if (totalQ1 == totalQ2) {
                break;
            }
            if (totalQ1 > totalQ2) {
                Long n = q1.poll();
                q2.offer(n);
                if (n == null) {
                    return -1;
                }
                totalQ1 -= n;
                totalQ2 += n;
                count++;
            }
            else {
                Long n = q2.poll();
                q1.offer(n);
                if (n == null) {
                    return -1;
                }
                totalQ1 += n;
                totalQ2 -= n;
                count++;
            }
            if (count >= len * 3) {
                return -1;
            }
        }
        
        return count;
    }
}

AI 코드

시간 복잡도: $O(n)$

---

배열을 이용해서

예)
1 2 1 2 1 10 1 2일 때,
left와 right로 나누어 범위를 변화시켜가며 값을 구함

배열의 활용법도 무궁무진 하다는 것을 깨달았음

---

class Solution {
    public long solution(int[] queue1, int[] queue2) {
        int n = queue1.length;
        long total = 0;
        for (int x : queue1) total += x;
        for (int x : queue2) total += x;
        if (total % 2 != 0) return -1;
        long target = total / 2;

        int[] merged = new int[2 * n];
        System.arraycopy(queue1, 0, merged, 0, n);
        System.arraycopy(queue2, 0, merged, n, n);

        long sum = 0;
        for (int i = 0; i < n; i++) sum += merged[i]; // 현재 queue1 역할의 합

        int left = 0, right = n; // [left, right)가 현재 queue1 역할의 윈도우
        int limit = 3 * n;
        for (int step = 0; step <= limit; step++) {
            if (sum == target) return step;
            if (sum > target) {
                sum -= merged[left++];
            } else {
                sum += merged[right++];
            }
        }
        return -1;
    }
}