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

 

프로그래머스

최초 접근방식 (93.3점, 통과못함)

큐는 단방향으로만 움직인다는 아이디어에 착안하여 큐 2개를 합쳐 하나의 배열로 만들고, 시작과 끝 인덱스 2개를 전진시키며 합산을 체크하는 방식으로 풀어보려고 했으나, 다 통과했는데 중간에 테스트케이스 2개를 끝끝내 통과하지 못했다. 예외처리를 해줘야할 부분이 있었던게 아닌가 싶은데 아쉽지만 이 접근 방식으로 답안을 완성하지는 못했다. 프로그래머스에서는 케이스를 공개하지 않는데 가끔은 이게 실제 프로그래밍 방식과 맞는 건지 의문이 들 때가 있다.

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        //queue1, queue2 합치기
        int[] arr = new int[queue1.length + queue2.length];
        int idx = 0;
        
        for(int i = 0; i < queue1.length; i++){
            arr[idx++] = queue1[i];
        }
        
        for(int i = 0; i < queue2.length; i++){
            arr[idx++] = queue2[i];
        }
        //전체 원소의 총합 구하기
        long total = 0;
        
        for(int i : arr){
            total += i;
        }
        
        if(total % 2 == 1){
            return -1;
        }
        
        int min = 600000;
        int i = 0;
        int j = 0;
        long sum = 0;
        
        while(i < arr.length && j < arr.length + queue1.length){
            
            sum += arr[j % arr.length];
                
            if(sum > total / 2){
                sum = sum - arr[i] - arr[j % arr.length];
                i++;
                continue;
            }
            
            if(sum == total / 2 && i + j - arr.length / 2 + 1 < min){
                min = i + j - arr.length / 2 + 1;    
            }
            
            j++;
        }
        
        return min == 600000 ? -1 : min;
    }
}

큐를 이용한 방식(통과)

문제 설명 그대로 풀어낸 방식인데 최소값을 구하기 위한 방법에서는 그리디를 적용했다. 그리디를 적용하는 기준은 각 큐의 합이였고, 합이 큰 쪽에서 작은쪽으로 숫자를 추출해서 더해주는 행위를 양쪽의 합이 같아질 때까지 반복하는 방식으로 접근했다. 반복문의 횟수 제한은 큐 하나의 길이의 4배(= 큐 2개를 합친 길이의 2배)로 정했는데, 이는 답이 나오지 않는 최악의 경우에 양쪽 큐가 원래의 상태로 돌아오기까지 필요한 횟수이기 때문이다.

 

로직설명

- int 배열 queue1, queue2로부터 두 개의 큐를 생성(q1, q2) 및 각각의 합(sum1, sum2) 구하기

- 양쪽 큐가 원래 상태로 돌아올때까지 반복:

1) sum1 > sum2인 경우: q1에서 poll() 후 q2에 add(), 각각의 합 증감

2) sum1 < sum2인 경우: q2에서 poll() 후 q1에 add(), 각각의 합 증감

3) sum1 == sum2인 경우: answer에 횟수 저장 후 반복 종료

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        
        int answer = -1;
        
        Queue<Integer> q1 = new LinkedList<Integer>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        
        long sum1 = 0;
        long sum2 = 0;
        
        for(int n : queue1){
            q1.add(n);
            sum1 += n;
        }
        
        for(int n : queue2){
            q2.add(n);
            sum2 += n;
        }

        int cnt = 0;
        
        while(cnt <= queue1.length * 4){
            if(sum1 > sum2){
                int poll = q1.poll();
                sum1 -= poll;
                sum2 += poll;
                q2.add(poll);
            }else if(sum1 < sum2){
                int poll = q2.poll();
                sum2 -= poll;
                sum1 += poll;
                q1.add(poll);
            }else if(sum1 == sum2){
                answer = cnt;
                break;
            }
            cnt++;
        }
    
        return answer;
    }
}

Note

- 가능하다면 최초 접근방식도 나중에 완성해보는 게 좋겠다.