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

문제 풀이

---

이 문제는 완전탐색을 활용해 풀기보다는 그리디 알고리즘을 활용해 풀어야 한다.

아아디어 도출

정직하게 문제에서 주어진대로 접근한다면 1번큐와 2번큐 중 추출시 선택의 기로가 생기게 되고, 결국 큐의 길이(최대 300,000)만큼 완전 탐색하며 경우의 수를 따지게 된다면 시간초과가 발생할 수 있다.

모든 큐의 합을 맟추려하지 말고, 아래처럼 접근하며 어떨까?

두 큐의 합이 같다 == 한 큐의 합은 두 큐의 합/2이 된다.

이 말은 즉, 1번 큐의 모든 원소의 합을 두 큐의 합/2의 값으로 만들면 된다는 것이다. 그렇다면 교체는 어떻게 하면 될까?

• 1번 큐의 합이 두 큐의 합/2 보다 작다면, 2번 큐에서 추출하여 가져온다.
• 1번 큐의 합이 두 큐의 합/2 보다 크다면, 1번 큐에서 추출하여 2번 큐로 넣어준다.

이때, 필자는 1번 큐를 기준으로 2번 큐를 교체할 큐로 정해 구현했다. 이제 위 내용을 통해 아이디어를 정리해보자.

1. 두 큐의 원소를 각각 큐에 저장하고, 1번 큐의 원소 합과 두 큐의 합/2의 값을 계산한다.(합 계산 중 문제 방지를 위해 long 타입을 사용!)
2. 1번 큐의 합(sum)이 두 큐의 합(total)과 같을 때까지 아래 3-4번 과정을 반복한다.
3. sum > total이라면 1번 큐에서 원소를 추출해 2번 큐로 삽입한다. 추출한 원소값만큼을 sum에서 뺀다.
4. sum < total이라면 2번 큐에서 원소를 추출하여 1번 큐로 삽입한다. 추출한 원소값만큼을 sum에 증가시킨다.
5. 이때, 교체횟수는 최대로 큐의 길이 * 3 만큼을 넘어갈 수 없기 때문에 반복 횟수가 이를 넘어가면 두 큐의 합을 맞출 수 없다고 판단하여 -1을 반환한다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    // 두 큐 원소의 합이 같다는 것은 하나의 큐의 합을 두 큐의 합/2 이 되면 된다는 것이다.

    public int solution(int[] queue1, int[] queue2) {

        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        // 문제에서 요구한대로 합 계산 과정 중 문제 방지를 위해 long 타입을 사용한다.
        long total = 0;
        long sum = 0;

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

        // 한쪽 큐의 합은 [두 큐의 합/2] 조건을 충족하면 된다.
        total /= 2;

        int cycle = queue1.length*3;
        int answer = 0;

        /**
         * 두 큐의 합을 동일하게 만드는 로직
         * q1을 기준으로 q2는 교체할 큐로 사용한다.
         * 단, 일정 교체횟수 이상을 반복하게 되면 종료한다.
         */
        while(sum != total) {

            /**
             * q1과 a2의 값을 교체하는 횟수는 최대 [한 큐의 길이 * 3] 만큼 을 넘지 않는다.
             * 교체 횟수 이상 반복되면 두 큐의 합을 맞추지 못하기에 -1을 반환한다.
             */
            if(cycle == 0) {
                return -1;
            }
            
            /**
             * q1의 합이 total보다 크다면, 첫번째 원소를 추출하고 q2의 원소를 가져온다.
             * 이때, q1의 합을 다시 계산하기 위해 추출한 수만큼을 뺀다.
             * 그 반대라면 q2의 첫번째 원소를 추출하고 q1의 원소를 가져간다.
             */
            if(sum > total) {
                int temp1 = q1.poll();
                sum -= temp1;
                q2.add(temp1);
            }
            else {
                int temp2 = q2.poll();
                sum += temp2;
                q1.add(temp2);
            }
            
            // 교체 횟수를 차감한다.
            cycle--;

        }

        // 두 큐의 합을 같게 한 이후, 총 교체횟수를 구한다.
        return queue1.length * 3 - cycle;
    }    

    public static void main(String[] args) {
        
        Solution sol = new Solution();
        
        // int[] queue1 = new int[]{3,2,7,2};
        // int[] queue2 = new int[]{4,6,5,1};
        int[] queue1 = new int[]{1,2,1,2};
        int[] queue2 = new int[]{1,10,1,2};
        
        sol.solution(queue1, queue2);

    }

}

회고

-

---

출처

-

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.