프로그래머스 - 두 큐 합 같게 하기

두 큐 합 같게 하기 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

---

Problem

---

Solve

두개의 큐가 가지는 각각의 합이 동일하도록 만들어지도록 해야합니다.

큐를 이동하는 총 횟수는 큐에 있는 모든 요소를 한바퀴 돈 경우로 생각하고 queue1.size()*2 + queue2.size()*2 로 요소 들의 이동의 최대값을 지정합니다.

그리고 최초 queue1의 합, queue2의 합을 초기화하고 큐가 가지는 합이 큰 곳의 큐에서 다른 큐로 요소를 이동시켜주도록 반복합니다.
(누적합을 이용함)

---

Code

import java.util.Queue;
import java.util.LinkedList;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
    	//queue1의 합
        long queue1Sum = 0;
        //queue2의 합
		long queue2Sum = 0;
		Queue<Integer> q1 = new LinkedList<>();
		Queue<Integer> q2 = new LinkedList<>();

		//queue1의 합 초기화
		for(int i=0;i<queue1.length;i++){
			q1.offer(queue1[i]);
			queue1Sum += queue1[i];
		}
        //queue2의 합 초기화
		for(int i=0;i<queue2.length;i++){
			q2.offer(queue2[i]);
			queue2Sum += queue2[i];
		}

		//반복의 최대 선언 (각 큐의 요소들이 다른 큐를 갔다가 본래 큐로 돌아오는 횟수)
		int limit = queue1.length* 2 +queue2.length*2;
		long target = (queue1Sum + queue2Sum)/2;

		//작업 횟수
		int count = 0;
        //queue1에 들어있는 합과 queue2에 들어있는 합이 target과 같을때까지 반복
		while(queue1Sum != target && queue2Sum != target){
        	//작업 횟수가 limit이상으로 넘어가면 더 이상 target을 만들 수 없기 때문에 -1 반환
			if(count > limit) return -1;

			//큐의 합이 더 큰곳에서 작은곳으로 요소를 하나씩 빼서 이동시킨다.
			if(queue1Sum > queue2Sum){
				int q = q1.poll();
				q2.offer(q);

				queue2Sum += q;
				queue1Sum -= q;
			}else{
				int q = q2.poll();
				q1.offer(q);

				queue1Sum += q;
				queue2Sum -= q;
			}
			count++;
		}

		return count;
    }
}

---

Result

문제 자체는 어렵지는 않았지만 반복을 중지하는 limit를 생각하는데 조금 오래걸렸다.

---

Reference