[Programmers] 두 큐 합 같게 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

문제 설명

두 큐의 합이 같도록 큐의 원소들을 enqueue, dequeue하는 문제이다. 문제 접근은 합이 큰 큐에서 작은 큐로 원소를 enqueue하는 방법을 두 큐의 합이 같아질 때까지 반복하도록 구현했다. 입력값이 int형이므로 총합이 홀수인 경우는 같게 할 수 없으므로 항상 -1을 반환한다. 시도 횟수에 제한을 두는 이유는 순환 문제 때문이다. [1, 1], [1, 5] 인 경우 총합은 짝수이지만 두 큐의 합이 같도록 만들 수 없다. 이런 경우에 대한 처리를 위해 두 큐의 원소 총합만큼 반복해도 되지 않는 경우에는 -1을 반환하도록 했다. 그런데 두 큐의 원소 총합보다 많은 시도 후에 같아지는 경우도 있다. [1, 1, 1, 1, 1], [1, 1, 1, 9, 1] 와 같은 경우인데 흐름을 나타내면 다음과 같다.

1. [1, 1, 1, 1, 1], [1, 1, 1, 9, 1] -> count = 0
2. [1, 1, 1, 1, 1, 1, 1, 1], [9, 1] -> count = 3 (오른쪽 큐의 1 세 개를 왼쪽 큐로 이동)
3. [1, 1, 1, 1, 1, 1, 1, 1, 9], [1] -> count = 4
4. [9], [1, 1, 1, 1, 1, 1, 1, 1, 1] -> count = 12 (왼쪽 큐의 1 여덟 개를 오른쪽 큐로 이동)

이런 문제를 처리하기 위해 한 쪽 큐가 다른 쪽 큐보다 작은 경우 커질 때까지 반복하도록 했다.

처음 조건

while (q1Total != q2Total) {
    attempt += 1;   

    if (attempt == limit) {
        return -1;
    } else if (q1Total > q2Total) {
        long elem = q1.poll();
        q2.offer(elem);
        q1Total -= elem;
        q2Total += elem;
    } else if (q2Total > q1Total) {
        long elem = q2.poll();
        q1.offer(elem);
        q2Total -= elem;
        q1Total += elem;
    }   
}

변경 후 조건

while (q1Total != q2Total) {  
    if (attempt >= limit) {
        return -1;
    }
            
    while (q1Total > q2Total) {
        long elem = q1.poll();
        q2.offer(elem);
        q1Total -= elem;
        q2Total += elem;
        attempt += 1; 
    }
            
    while (q2Total > q1Total) {
        long elem = q2.poll();
        q1.offer(elem);
        q2Total -= elem;
        q1Total += elem;
        attempt += 1;
    }
}

코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Long> q1 = new LinkedList<>();
        Queue<Long> q2 = new LinkedList<>();
        
        int attempt = 0;
        int limit = queue1.length + queue2.length;
        long q1Total = 0L;
        long q2Total = 0L;
        
        for (int elem : queue1) {
            q1.offer(Long.valueOf(elem));
            q1Total += elem;
        }
        
        for (int elem : queue2) {
            q2.offer(Long.valueOf(elem));
            q2Total += elem;
        }
        
        if ((q1Total + q2Total) % 2 == 1) {
            return -1;
        }
        
        while (q1Total != q2Total) {  
            if (attempt >= limit) {
                return -1;
            }
            
            while (q1Total > q2Total) {
                long elem = q1.poll();
                q2.offer(elem);
                q1Total -= elem;
                q2Total += elem;
                attempt += 1; 
            }
            
            while (q2Total > q1Total) {
                long elem = q2.poll();
                q1.offer(elem);
                q2Total -= elem;
                q1Total += elem;
                attempt += 1;
            }
        }
        
        return attempt;
    }
}