[Programmers] 두 큐 합 같게 만들기 Java

반응형

728x90

[Programmers] 두 큐의 합 같게 만들기 - LV 2

---

접근

• 구현

---

풀이

양 쪽 큐의 원소를 옮겨가며  총원소의 합이 같게 만들어야 하는 문제이다. 큐 1의 원소를 큐 2로 삽입하는 것까지의 과정이 1번의 연산으로 같게 만들 수 없는 경우 -1을 출력한다.

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

        long sum1 = 0;
        long sum2 = 0;

일단 큐에 넣어줘야 연산을 진행할 수 있으니 배열로 된 값들을 큐에 넣어주는데 이 문제에서 큐의 길이도 상당히 크지만 원소의 최댓값도 말도 안 되게 크기 때문에 무조건 long 타입을 사용해 주어야 오버플로우가 나지 않는다.

	for (int num : queue1) {
            sum1 += num;
            q1.offer((long) num);
        }
        for (int num : queue2) {
            sum2 += num;
            q2.offer((long) num);
        }

        long totalSum = sum1 + sum2;

각각 배열의 값을 다 큐에 넣어준 뒤 두 큐에 들어있는 총원소의 합을 구해줬다.

	if (totalSum % 2 != 0)
            return -1;

        long target = totalSum / 2;
        int operations = 0;
        int maxOperations = (queue1.length + queue2.length) * 2;
        
        return makeSameQueue(operations, maxOperations, sum1, target, q1, q2, sum2);

총원소의 합이 반으로 나눠 떨어지지 않는다면 어떤 방법을 써도 양쪽 큐를 같은 값으로 맞출 수 없기에 -1을 리턴한다. 총원소의 합이 짝수라면 절반을 나눠 각 큐의 합이 될 값을 구한다. 연산 횟수를 저장할 변수와 총 연산 횟수를 가지는 변수를 선언한다. 총 연산 횟수는 while 문으로 수행을 진행하여 총 연산 횟수 이상 진행을 하게 되면 불가능한 경우로 -1을 반환하기 위함인데 정확하게 몇 번 수행을 해야 모든 경우의 수를 수행해 볼 수 있는지 계산을 안 해봐서 적당히 양쪽 큐의 길이를 합친 것에 두 배를 해주었다. 코드가 정확하게 동작하는 것을 보장하고 연산이 가능한 경우 maxOperations의 수가 크든 말든 상관이 없지만 이리저리 옮겨도 불가능한 경우 maxOperations의 횟수만큼 반복을 진행한 뒤 루프가 끝나기 때문에 적당한 값을 사용해야 한다. 이 문제에서 큐의 최대 길이는 300,000으로 (300,000 + 300,000) x 2 = 1,200,000으로 시간 안에는 충분히 수행 가능한 횟수이기 때문에 문제가 되지는 않는다.

    private int makeSameQueue(int operations, int maxOperations, long sum1, long target, Queue<Long> q1, Queue<Long> q2, long sum2) {
        while (operations <= maxOperations) {
            if (sum1 == target) {
                return operations;
            }

메인 로직이 들어있는 메서드로 코드를 쭉 짠 다음에 함수로 뽑았더니 파라미터가 참 많이 생겨버렸다. while문은 총 연산 횟수를 넘어가게 되거나 현재 큐의 총합이 기준 값이 맞춰지게 되면 종료가 된다.

	    if (sum1 > target) {
                long moved = q1.poll();
                sum1 -= moved;
                q2.offer(moved);
                sum2 += moved;
            } else {
                long moved = q2.poll();
                sum2 -= moved;
                q1.offer(moved);
                sum1 += moved;
            }
            operations++;
        }
        return -1;

현재 큐의 총 합이 맞춰야 할 기준과 다르다면 작은 합이 큰 쪽 큐에서 원소를 뽑아 작은 쪽 큐로 옮기는 코드이다. 큰 쪽에서 원소를 뽑은 뒤 합계 변수에서 값을 빼주고 작은 쪽 큐로 옮겨 넣은 뒤 자은 쪽 합계 변수에 값을 더해준다. 한 번의 연산이 끝나게 되면 operations의 값을 올려 연산 횟수를 증가시켜주고 while문이 끝나게 되면 양쪽을 동일한 값으로 맞추지 못했으므로 -1을 반환하게 된다.

---

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Long> q1 = new LinkedList<>();
        Queue<Long> q2 = new LinkedList<>();

        long sum1 = 0;
        long sum2 = 0;

        for (int num : queue1) {
            sum1 += num;
            q1.offer((long) num);
        }
        for (int num : queue2) {
            sum2 += num;
            q2.offer((long) num);
        }

        long totalSum = sum1 + sum2;

        if (totalSum % 2 != 0)
            return -1;

        long target = totalSum / 2;
        int operations = 0;
        int maxOperations = (queue1.length + queue2.length) * 2;

        return makeSameQueue(operations, maxOperations, sum1, target, q1, q2, sum2);
    }

    private int makeSameQueue(int operations, int maxOperations, long sum1, long target, Queue<Long> q1, Queue<Long> q2, long sum2) {
        while (operations <= maxOperations) {
            if (sum1 == target) {
                return operations;
            }
            if (sum1 > target) {
                long moved = q1.poll();
                sum1 -= moved;
                q2.offer(moved);
                sum2 += moved;
            } else {
                long moved = q2.poll();
                sum2 -= moved;
                q1.offer(moved);
                sum1 += moved;
            }
            operations++;
        }

        return -1;
    }
}