[Progammers] 두 큐 합 같게 만들기

dev_yuni·2024년 11월 27일

알고리즘 프로그래머스

알고리즘

목록 보기

3/6

👀 문제 분석

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

길이가 같은 두 개의 큐가 주어진다. 하나의 큐를 골라서 원소를 추출하고 추출된 원소를 다른 큐에 집어넣는 작업을 통해서 각 큐의 원소 합이 같도록 만든다.

이때 필요한 최소 작업 수를 반환하면 된다. pop - insert 쌍이 1회 수행으로 간주된다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return한다.
단, 어떤 방법으로도 합을 같게 만들지 못하면 -1을 return 한다.

⚒️ 설계

입력된 queue1과 2의 원소를 각 큐에 저장한다.
각 큐에 저장된 값의 총 합을 구한다.
두 큐의 원소 합이 홀수라면, 두 큐를 같은 합으로 만드는 것이 불가능하므로 -1을 반환한다.
총합을 2로 나눈 값을 목표 값으로 설정한다.
각 큐의 합이 목표 값이 될 때까지 원소를 하나씩 다른 큐로 이동한다.
현재 합이 목표 값보다 작다면, queue2에서 원소를 하나 꺼내 queue1에 추가하고, 크다면, queue1에서 원소를 하나 꺼내 queue2에 추가한다.
각 이동 시, 이동 횟수를 증가시키고 총 이동 횟수가 가능한 최대 이동 횟수를 초과하면 -1을 반환한다.

여기서 가능한 최대 이동 횟수는 무한 루프를 방지하기 위해 상한 값으로 설정한 것입니다.
큐의 길이가 고정되어 있고 두 큐를 순환하기 때문에 최악의 경우 두 큐 간에 한 번씩 모두 이동하기 때문에 이동 연산이 발생합니다.
만약, 한 큐에서 다른 큐로 이동했는데 다시 원소를 되돌려야하는 상황이 발생했을 경우도 고려하면 3번 반복되기 때문에 최대 이동 횟수를 (두 큐의 길이 * 3) 을 상한값으로 설정했습니다.

📝 코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        long sum1 = 0, sum2 = 0;

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

        long totalSum = sum1 + sum2;
        if (totalSum % 2 != 0) {
            return -1;
        }

        long target = totalSum / 2;
        int moveCount = 0, maxMoves = 3 * (queue1.length + queue2.length);

        while (moveCount <= maxMoves) {
            if (sum1 == target) {
                return moveCount;
            }

            if (sum1 < target) {
                int value = q2.poll();
                q1.offer(value);
                sum1 += value;
                sum2 -= value;
            } else {
                int value = q1.poll();
                q2.offer(value);
                sum1 -= value;
                sum2 += value;
            }
            moveCount++;
        }
        return -1;
    }

}

⌛️ 시간복잡도

큐 초기화: $O(n_1 + n_2)$
while 루프: $O(n_1 + n_2)$
여기서 N을 두 큐 원소 개수의 합으로 정의하면 최종 시간 복잡도는 $O(N)$ 이다.

❗️ 다른 풀이

다른 사람들의 풀이를 보니 큐를 사용하지 않고 하나의 배열을 사용한 풀이가 많았다. 그래서 배열을 사용해 풀이를 해보았다.

public int solution(int[] queue1, int[] queue2) {
    long sum1 = Arrays.stream(queue1).asLongStream().sum();
    long sum2 = Arrays.stream(queue2).asLongStream().sum();
    long totalSum = sum1 + sum2; // 두 큐의 합 (전체 배열 합)

    // 전체 합이 홀수면 두 큐를 동일하게 나눌 수 없음.
    if (totalSum % 2 != 0) return -1;

    long target = totalSum / 2; // 목표 합

    // 두 배열을 하나로 결합
    int[] merged = new int[queue1.length + queue2.length]; 
    System.arraycopy(queue1, 0, merged, 0, queue1.length);
    System.arraycopy(queue2, 0, merged, queue1.length, queue2.length);

    // 투 포인터 설정
    int start = 0, end = queue1.length; // start는 첫 번째 큐의 시작점, end는 두 번째 큐의 시작점
    long current = sum1; // 현재 첫 번째 큐의 합으로 초기화
    int moveCount = 0; // 이동 횟수
    int maxMoves = 3 * merged.length;

    // 투 포인터를 활용하여 목표 합에 도달할 때까지 반복
    while (moveCount <= maxMoves) {
        if (current == target) return moveCount; // 목표 합에 도달하면 이동 횟수 반환

        // 현재 합이 목표보다 작은 경우: 큐2에서 큐1로 원소를 추가
        if (current < target) {
            current += merged[end % merged.length]; // end가 가리키는 값을 더함
            end++; // end 포인터를 오른쪽으로 이동
        } 
        // 현재 합이 목표보다 큰 경우: 큐1에서 원소를 제거
        else {
            current -= merged[start % merged.length]; // start가 가리키는 값을 뺌
            start++; // start 포인터를 오른쪽으로 이동
        }
        moveCount++; // 이동 횟수 증가
    }

    // 반복이 끝났음에도 목표를 달성하지 못한 경우, -1 반환
    return -1;
}