[Algorithm] 프로그래머스 - 두 큐 합 같게 만들기 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 - 두 큐 합 같게 만들기 자바 풀이를 정리하도록 하겠습니다.

 

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/118667#

프로그래머스

 

 

 

1. 풀이 소스:

 

import java.util.*;

class Solution {
    
    public int solution(int[] arr1, int[] arr2) {
        
        long arr1Sum = 0L; // 합을 위한 long 타입 초기화
        long arr2Sum = 0L;
        
        Queue<Integer> arr1Queue = new ArrayDeque<>();
        Queue<Integer> arr2Queue = new ArrayDeque<>();
        
        for (int i : arr1) {
            arr1Sum += i;
            arr1Queue.add(i);
        }
        for (int i : arr2) {
            arr2Sum += i;
            arr2Queue.add(i);
        }
        
        if (arr1Sum == arr2Sum) return 0; // 이미 합이 한 번에 같다면 종료
        
        EqualSum es = new EqualSum(arr1Sum, arr2Sum, arr1Queue, arr2Queue);
        
        return es.find();
    }

}

class EqualSum {
    
    int totalJob; // 최소 수행 과정
    int limit; // 무한 루프 제한 조건
    QueueSize big; // 합이 큰 Queue를 저장하려는 참조 QueueSize 인스턴스
    QueueSize small; // 합이 작은 Queue를 저장하려는 참조 인스턴스
    
    class QueueSize {
        long sum; // 합 저장
        Queue<Integer> queue; // 큐 참조
    
        QueueSize(long sum, Queue<Integer> queue) {
            this.sum = sum; 
            this.queue = queue;
        }  
    }
    
    EqualSum(long arr1Sum, long arr2Sum, Queue<Integer> arr1Queue, Queue<Integer> arr2Queue) {            
        if (arr1Sum >= arr2Sum) { // arr1Sum이 더 크면 big에 arr1Queue, small = arr2Queue
            big = new QueueSize(arr1Sum, arr1Queue);
            small = new QueueSize(arr2Sum, arr2Queue);         
            
        } else { // arr2Sum이 더 크다면 big에 arr2Queue 설정, small = arr1Queue
            big = new QueueSize(arr2Sum, arr2Queue);
            small = new QueueSize(arr1Sum, arr1Queue);
        }
        
        // 참조 #1
        limit = big.queue.size() * 3; // 한계치 설정을 위해 limit에 큐 크기 * 3 
    }
    
    void swap() { // 만약 queue에 있는 sum 크기가 달라진다면 swap으로 queue 참조 바꾸기
        QueueSize tmp = null; // swap을 위한 QueueSize tmp 생성
        if (big.sum < small.sum) {
            tmp = small;
            small = big;
            big = tmp;
        }
    }
    
    int find() {
        
        // 참조 #2
        while(!big.queue.isEmpty() && !small.queue.isEmpty()) { // 큐에서 더 이상 뺄 수 없는 경우 종료

            int pop = big.queue.poll(); // 합이 더 큰 queue에서 빼기
            small.queue.add(pop); // 작은 큐에 더하기
            
            big.sum -= pop; // 빅 큐 합 업데이트
            small.sum += pop; // 스몰 큐 합 업데이트
            totalJob++; // totalJob 업데이트
            
            if (big.sum == small.sum) return totalJob; // 두 큐의 합이 같다면 종료    
            if (big.sum < small.sum) swap(); // 만약 스몰 큐의 합이 더 크면 스왑
            
            if (totalJob > limit) break; // 큐 교체의 한계보다 더 크다면 무한 루프 해제
        }
        
        return -1; // 두 큐의 합을 같게 만들 수 없음
    }
}

 

 

 

 

2. 풀이 과정

 

해당 문제는 Queue1, Queue2에 대한 참조를 바꿔가며 합이 더 큰 큐에서 작은 큐로 이동하여 합을 비교하는 방식으로 문제를 풀이해야 합니다.

 

이러한 과정이 가능한 이유는 Big 큐는 Small 큐보다 무조건 크기 때문에 Big에서 Small 큐로 원소를 옮기다 보면
어느 순간 같게 되는 상황이 생길 수 있기 때문입니다.

 

예를 들면 아래의 테스트 케이스가 존재합니다.

 

Big : 1 100

Small: 1 98

 

Big : 100

Small: 1 98 1

 

하지만 Big Queue에서 Small Queue로 옮기다 보면 Small Queue가 더 커질 수 있습니다. 이 경우 Swap을 통해
참조를 바꿔주어야 합니다.

 

Big : 1 100 2

Small: 1 1 97

 

Big: 100 2

Small : 1 1 97 1

 

Big : 2

Small: 1 1 97 1 100

 

<Swap>

 

Big: 1 1 97 1 100

Small: 2

---- 진행 ----

 

Big: 1 100

Small: 2 1 1 97 이 완성됩니다.

 

 

3. 종료 조건 

 

주석 참조 #1, 참조#2는 무한 루프에 빠지지 않도록 종료하는 것입니다.

 

참조#2

 

Big: 1 5

Small: 1 1 

 

Big : 5

Small : 1 1 1

 

여기서 Big에서 하나 더 뺀다면 Big의 큐가 비워져 버립니다.

이를 고려하면 결국 다시 Small에서 Big을 스왑하고 Big에 Queue 참조를 옮겨야 합니다. 

 

Big : X (X는 Big의 원소의 합)

Small: Y(Y는 Small의 원소의 합)

 

Big: 0 

Small : Y + X  

X > Y 었으므로  원소의 합인 Y보다 Big에 옮겨지는 큐 원소는 모든 원소의 합 Y > (부분 원소 합)이 만족합니다. 따라서,

 

Big : Y 

Small : X 가 될 때까지 반복하게 됩니다. 

이 경우 스왑하면 다시 원점으로 돌아가게 되므로 종료 조건에 포함됩니다.

 

 

참조#1

 

Queue의 길이에 * 3인 이유는 아래의 케이스를 확인하면 볼 수 있습니다.

 

두 큐가 마지막 스왑하기 전까지 특정 원소는 한 번씩만 이동한다면 바뀔 수 있는 최대 경우는 하나씩 교체하는 것입니다.

(Q1.size = Q2.size = n일 때, Q1 -> Q2로 이동후 Q2 -> Q1에서 반절의 개수만큼 이동시 2n, 하나씩 교체를 하는 경우 3n)

 

Q1: 1 2 3

Q2: 4 5 6

 

Q1: 2 3

Q2: 4 5 6 1

 

Q1: 2 3 4

Q2: 5 6 1

 

Q1: 3 4

Q2: 5 6 1 2

 

Q1: 3 4 5

Q2: 6 1 2

 

Q1: 4 5 

Q2: 6 1 2 3

 

Q1: 4 5 6

Q2 : 1 2 3

 

추가로 루프에 빠지고 있지 않는지 확인하는 테스트 케이스를 제공하겠습니다.!

테스트 추가 : [1000, 1000], [500, 400], [-1] 

 

자세한 설명은 주석으로 처리하였습니다.!

이상으로 프로그래머스 두 큐 합 같게 만들기 풀이를 마치도록 하겠습니다. 감사합니다.!