programmers - 두 큐 합 같게 만들기

문제 분석

1. 두큐 queue1, queue2에서 pop + insert = 1회 작업으로 각 큐의 합을 같게 만드는 최소 작업 수를 구하는 문제

2. pop은 맨 앞, insert는 맨 뒤에 수행

3. 큐는 한 방향으로만 pop, insert 가능

4. 방법이 없으면 -1 리턴

 

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

 

queue1의 합 = 14

queue2의 합 = 16

 

전체합 = 30 -> 반으로 나눈 15가 목표임

 

queue1의 합을 14 -> 15로 올리고, queue2의 합을 16 -> 15로 줄이는 방향으로 원소를 이동시켜야함.

 

주의 사항

브루트 포스 접근 방식으로하면 배열 크기가 최대 300000이기에 불가능

int형의 범위를 넘어가니 long타입 사용해야함

 

알고리즘 방식

목표: queue1, queue2의 합을 같게 만드는 최소 pop + insert 횟수 계산하기

-> 두 큐를 합쳐서 같은 합의 두 파트로 나누는 최소 이동 시뮬레이션

 

구현 방법

주어진 두 큐를 이어서 슬라이딩 윈도우 방식으로 알고리즘을 구현해 주었습니다.

 

슬라이딩 윈도우로 구현하기 위해서는 두 큐를 합쳐서 구현을 해줘야합니다.

 

    // 큐4개를 이은 배열 선언(그래야 슬라이딩 윈도우로 접근 가능)
        long[] arr = new long[n*4];

 

큐 4개를 이어줘야 슬라이딩 윈도우같이 한쪽에서 빼고 한쪽에서 넣어주는 방식이 가능합니다.

 

// 선언해준 배열에 두 큐 넣기
        for(int i = 0; i< n; i++) {
            arr[i] = queue1[i];
            arr[i + n] = queue2[i];
            arr[2*n + i] = queue1[i];
            arr[3*n + i] = queue2[i];
            // 총합 구해주기 위해 계산
            total += queue1[i] + queue2[i];
        }

 

그 후 선언한 배열에 두 큐를 넣어줍니다.

 

이때 만약 총합이 짝수가 아니라면 -1를 리턴해야하므로(두 큐의 합이 같아질 수 없음) 예외처리를 진행해줍니다.

// 만약 총합이 짝수가 아니면 두 큐의 합이 같게 될수 없으므로 예외처리
        if(total % 2 != 0) {
            return -1;
        }

 

그 후 우리의 목적은 두 큐의 합이 같은거니까 총 합의 절반을 target으로 잡아준후 시작점을0, 끝나는점을 n이라고 잡아줍니다

그리고 이 한 큐에서의 총 합을 구해줍니다.

 long target = total/2;
        long currentSum = 0;
        int start = 0;
        int end = n;
        
        for(int i = 0; i<n; i++) {
            currentSum += queue1[i];
        }

 

 

그 후 답인 count를 기준으로 while문을 통해 end지점이 배열의 끝 지점까지 될때까지 돌려주며 안에서 슬라이딩 윈도우 기법으로

판별해주며 구현해주었습니다.

  int count = 0;
        int maxOperation = n*3;
        
        while(start <= end && end < arr.length && count <= maxOperation) {
            if(currentSum == target) {
                return count;
            } else if (currentSum < target) {
                currentSum += arr[end];
                end++;
            } else {
                currentSum -= arr[start];
                start++;                
            }
            count++;
        }

 

 

최종 코드

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int n = queue1.length;
        long total = 0;
        
        // 큐4개를 이은 배열 선언(그래야 슬라이딩 윈도우로 접근 가능)
        long[] arr = new long[n*4];
        
        // 선언해준 배열에 두 큐 넣기
        for(int i = 0; i< n; i++) {
            arr[i] = queue1[i];
            arr[i + n] = queue2[i];
            arr[2*n + i] = queue1[i];
            arr[3*n + i] = queue2[i];
            // 총합 구해주기 위해 계산
            total += queue1[i] + queue2[i];
        }
        
        // 만약 총합이 짝수가 아니면 두 큐의 합이 같게 될수 없으므로 예외처리
        if(total % 2 != 0) {
            return -1;
        }
        
        long target = total/2;
        long currentSum = 0;
        int start = 0;
        int end = n;
        
        for(int i = 0; i<n; i++) {
            currentSum += queue1[i];
        }
        
        int count = 0;
        int maxOperation = n*3;
        
        while(start <= end && end < arr.length && count <= maxOperation) {
            if(currentSum == target) {
                return count;
            } else if (currentSum < target) {
                currentSum += arr[end];
                end++;
            } else {
                currentSum -= arr[start];
                start++;                
            }
            count++;
        }
        
        return -1;
        
        
    }
}