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

https://school.programmers.co.kr/questions/80612

프로그래머스

접근 방법

1. enqueue와 dequeue를 통해 원소를 옮겨가며 queue1과 queue2의 합이 서로 같도록해야한다 -> queue1의 원소를 관리하고 나머지는 queue2로 볼 수  있다.
2. 두 큐를 하나의 배열로 잇고 각 sum1과 sum2가 같도록한다 즉, 합이 큰 큐에서 작은 큐로 원소를 옮긴다.
3. 큐가 빈다면 답을 구할 수 없는경우이다.

 

코드

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int n = queue1.length;
        long sum1 = 0;
        long sum2 = 0;
        int[] arr = new int[2*n];
        
        //각 큐의 합을 구하고, 하나의 배열로 큐를 잇는다
        for(int i = 0 ; i < n ; i++){
            sum1 += queue1[i];
            sum2 += queue2[i];
            arr[i] = queue1[i];
            arr[i+n] = queue2[i];
        }
        
        
        int l = 0; // l ~ r-1 이 queue1의 범위
        int r = n; // r ~ 2n-1이 queue2의 범위
        int ans = 0;
        
        while(l < r){
			 //각 큐의 합이 같으면 연산횟수 리턴
            if(sum1 == sum2) return ans;
            
            ans++;
            
            //합이 큰 큐에서 작은 큐로 원소를 옮긴다
            //큐가 빈다면 원하는 값을 얻지 못하는 경우이다.
            if(sum1 > sum2){
                sum1 -= arr[l];
                sum2 += arr[l];
                l++;
            }else{
                sum1 += arr[r];
                sum2 -= arr[r];
                r++;
                if(r == 2*n) return -1;
            }
        }
        return -1;
    }
}