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

문제

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

프로그래머스

 

문제 분석

큐 2개가 주어지고 두 큐의 원소의 합이 같도록 하기 위해서 몇번의 연산이 필요한 지 묻는 문제이다.

큐에서 원소 하나를 빼고 넣는 과정을 연산 1번 일어난 것으로 계산한다.

 

원소 하나의 크기가 최대 10^9 이기 때문에 원소의 합을 구하는 과정에서 int 의 크기를 초과한다. 

 

문제 접근

원소의 합이 큰 큐에서 빼서 합이 작은 큐에 넣는 과정을 반복하면 제일 빠르게 두 큐의 원소의 합이 같아진다.

문제는 두 큐의 합이 같아질 수 없는 경우가 있는데 이때는 얼마나 반복해야 두 큐의 합이 같지 않다는 것을 증명할 수 있는가이다.

 

한쪽 큐에서 다른쪽 큐로 전부 넘어 왔다가 다시 돌아오고 다른 쪽 큐도 마찬가지로 생각해 본다면 큐의 길이 4배 정도 계산했을 경우에도 같아지지 않는다면 같을 수 없다고 판단할 수 있다.

 

코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int result = 0;
        Queue<Integer> queueOne = Arrays.stream(queue1)
                .boxed()
                .collect(Collectors.toCollection(LinkedList::new));

        Queue<Integer> queueTwo = Arrays.stream(queue2)
                .boxed()
                .collect(Collectors.toCollection(LinkedList::new));

        long sumOne = queueOne.stream().mapToLong(Integer::longValue).sum();
        long sumTwo = queueTwo.stream().mapToLong(Integer::longValue).sum();

        int size = queue1.length * 4;
        for (int i = 0; i < size; i++) {
            if (sumOne == sumTwo) {
                return result;
            }

            if (sumOne < sumTwo) {
                int num = queueTwo.poll();
                queueOne.offer(num);
                sumTwo -= num;
                sumOne += num;
                result++;
            }else{
                int num = queueOne.poll();
                queueTwo.offer(num);
                sumOne -= num;
                sumTwo += num;
                result++;
            }
        }

        return -1;
    }
}