2022 KAKAO TECH INTERNSHIP | 두 큐 합 같게 만들기

문제는 두 큐가 주어졌을 때 enqueue, dequeue 연산만으로 두 큐의 합이 정확히 반씩 나눠지도록 연산을 수행하는 것인데, 최소로 수행해야한다고 한다.

 

queue1의 합을 L, queue2의 합을 R이라고 했을 때, L과 R을 같게 만들기 위해서는 탐욕법을 사용하여 해결 할 수 있다.

 

- L > R 이라면, q1의 원소를 q2으로 넘긴다.

- L < R 이라면, q2의 원소를 q1으로 넘긴다.

 

L > R인 상황에서 먼저 L을 증가시키고 R을 감소시키는 방법이 최적인 경우가 있다고 가정해보자. 이 경우 L = R을 만들기 위해서 언젠가 L을 감소시키고 R을 증가시켜야 하고 결국 q1의 원소를 q2로 넘겨주는 동작은 반드시 필요하다. 

 

이 때 직접 큐 자료구조를 사용하지 않고 단순히 배열을 큐로 사용하면 0번 원소를 지우는 과정에서 시간 초과가 발생할 수도 있다. 

 

PY

from collections import deque

def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    q1_sum = sum(queue1)
    half_total_sum = (q1_sum + sum(queue2)) // 2  # 두 큐 합의 절반
    cnt = 0

    while queue1 and queue2:
        if q1_sum == half_total_sum:  # 두 큐 합이 같으면 종료
            return cnt
        elif q1_sum > half_total_sum:  # queue1의 합이 더 크면 queue1에서 빼기
            q1_sum -= queue1.popleft()
        else:  # queue1의 합이 queue2보다 작을 때
            queue1.append(queue2.popleft())
            q1_sum += queue1[-1]
        cnt += 1

    return -1  # 두 큐 합이 같아지지 않으면 -1 반환

 

JS

function solution(queue1, queue2) {
    const arr = [...queue1, ...queue2];
    let start = 0;
    let end = (arr.length / 2) - 1;

    let cnt = 0;
    let answer = -1;

    let leftSum = 0;
    let rightSum = 0;
    for(let i = start; i <= end; i++) {
        leftSum += arr[i];
    }

    for(let i = end + 1; i < arr.length; i++) {
        rightSum += arr[i];
    }

    while(cnt <= arr.length + 2) {
        if(leftSum === rightSum) {
            answer = cnt;
            break;
        }else if(leftSum > rightSum) {
            leftSum -= arr[start];
            rightSum += arr[start];
            start++;
        }else {
            end++;
            rightSum -= arr[end];
            leftSum += arr[end];
        }
        cnt++;
    }
    return answer;
}