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

문제 설명

 

프로그래머스

 

접근 방법

우선 주어지는 두 배열을 각각 큐로 변환해서 접근했습니다.

 

        int length = queue1.length;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        for (int i = 0; i < length; i++) {
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }

 

이후 두 큐의 합(sum1, sum2)을 구하고, 무한 반복문을 순회하면서 sum1과 sum2를 비교하면서 같아질 때까지 디큐 및 엔큐를 해주면서 작업 횟수를 카운팅해줍니다. 이때 최초 sum1 = sum2 조건을 만족한 경우의 작업 횟수가 곧 문제에서 요구하는 최소 작업 횟수가 됩니다. 또한 sum1과 sum2는 처음에만 요소들의 합으로 초기화해주고 이후에는 디큐 및 엔큐되는 요소를 해당 변수들(sum1, sum2)에 반영해주면됩니다. 굳이 매번 작업 때마다 sum1과 sum2를 구하기 위해 큐를 순회할 필요없다는 게 포인트입니다.

 

        long sum1 = getSum(q1), sum2 = getSum(q2);
        int result, count = 0;
        while (true) {
            if (sum1 > sum2) {
                Integer i1 = q1.poll();
                q2.add(i1);
                sum1 -= i1;
                sum2 += i1;
                count++;
            } else if (sum1 < sum2) {
                Integer i2 = q2.poll();
                q1.add(i2);
                sum1 += i2;
                sum2 -= i2;
                count++;
            } else {
                result = count;
                break;
            }
        }

    private long getSum(Queue<Integer> queue) {
        long sum = 0;
        for (Integer i : queue) {
            sum += i;
        }

        return sum;
    }

 

하지만 이렇게 sum1 = sum2 조건을 충족한 후 무한 반복문을 break 하면 다행이지만, 특정 경우에선 이러한 디큐 및 엔큐 작업으론 sum1 = sum2 조건을 충족 못하는 경우도 발생할 수 있습니다. 이러한 경우를 알기 위해서는 큐를 가장 오래 순회하게되는 경우의 작업 횟수에 대해 알아야 합니다.

 

만일 큐1과 큐2의 길이가 5라고 했을 때, 요소가 최초 큐1에 있는 4번째 요소(x)와 나머지 요소들의 합이 같다고 가정해보겠습니다. 

 

 

이 경우 sum1 = sum2 조건을 확인하기 위해서는 총 12번의 작업이 필요합니다. 만일 12번의 작업으로도 sum1 = sum2 조건을 충족시키지 못한다면, 곧이어 13번의 작업을 수행함에 있어 이는 불필요한 작업들을 반복하게 되는 꼴이 됩니다.

 

따라서 13번의 작업을 수행했을 때 추가 작업을 하지 않도록 해주어야 하며, 이를 탈출 조건 식으로 나타내면, 다음과 같습니다.

 

작업 회수(count) > 최초 큐의 길이 * 2 + 2

 

        while (true) {
            if (count > 2 * length + 2) {
                return -1;
            } 
            
            // ...

 

나의 소스 코드

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public int solution(int[] queue1, int[] queue2) {
        int length = queue1.length;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        for (int i = 0; i < length; i++) {
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
        
        long sum1 = getSum(q1), sum2 = getSum(q2);
        int result, count = 0;
        while (true) {
            if (count > 2 * length + 2) {
                return -1;
            } else if (sum1 > sum2) {
                Integer i1 = q1.poll();
                q2.add(i1);
                sum1 -= i1;
                sum2 += i1;
                count++;
            } else if (sum1 < sum2) {
                Integer i2 = q2.poll();
                q1.add(i2);
                sum1 += i2;
                sum2 -= i2;
                count++;
            } else {
                result = count;
                break;
            }
        }

        return result;
    }

    private long getSum(Queue<Integer> queue) {
        long sum = 0;
        for (Integer i : queue) {
            sum += i;
        }

        return sum;
    }
}

 

참고자료

• https://school.programmers.co.kr/learn/courses/30/lessons/118667