[Jacoste] 알고리즘 공부

<두 큐 합 같게 만들기>는 인자로 주어지는 두 배열(큐)의 합을 같게 만드는 문제다. 문제를 보고 가장 먼저 든 생각은 "큐를 만들어야 한다!"였다.

하지만 문제에서 이미 큐를 배열로 주기 때문에 따로 생성할 필요는 없다. 그냥 주어진 배열을 shift(), push() 메서드로 요리조리 움직이며 계산해 보자고 해서 나온 것이 아래의 식이다. 합이 더 큰 큐에서 합이 더 작은 큐로 이동시키며 값을 확인하는 형식으로 구현했다.

function solution(queue1, queue2) {
    const goal = (queue1.reduce((a, b) => a + b) + queue2.reduce((a, b) => a + b)) / 2;
  	// 맞춰야 하는 한쪽 큐의 합(두 큐의 합 / 2)
  
    if (Math.max(...queue1, ...queue2) > goal || goal % 1) return -1;
  	// 최댓값이 goal보다 크거나, goal이 홀수인 경우 두 큐의 합을 맞출수 없으므로 -1 반환
  
    let move = 0;
    
    while (1) {
        const sum = queue1.reduce((a, b) => a + b, 0);
      
        if (sum === goal) break;
        else {
            if (sum > goal) queue2.push(queue1.shift());
          	// queue1의 합이 더 큰 경우 queue1[0]을 queue2로 이동
            else queue1.push(queue2.shift());
          	// queue2의 합이 더 큰 경우 queue2[0]을 queue1로 이동
            move += 1;
        }
    }
    return move;
}

위의 식에서 가장 큰 문제는 반복문에 탈출 조건이 없다는 것이다. 문제에서는 두 큐의 합을 같게 맞출 수 없는 경우 -1을 반환하라고 명시되어 있다.

그렇게 해서 생각해 본 최악의 경우의 수는 queue1.length * 2였다. queue1의 모든 요소가 queue2로 이동하고, queue1의 모든 요소가 queue1로 넘어오는 경우를 생각했다.

function solution(queue1, queue2) {
    const goal = (queue1.reduce((a, b) => a + b) + queue2.reduce((a, b) => a + b)) / 2;
    if (Math.max(...queue1, ...queue2) > goal || goal % 1) return -1;
  
    let move = 0;
    
    while (move <= queue1.length * 2) {
    // 반복문 탈출 조건 추가(최악의 경우)
        const sum = queue1.reduce((a, b) => a + b, 0);
      
        if (sum === goal) break;
        else {
            if (sum > goal) queue2.push(queue1.shift());
            else queue1.push(queue2.shift());
            move += 1;
        }
    }
    return move;
}

그래도 안되는 내 코드. 무엇이 문제인지 찾아보니 자바스크립트는 큐를 자체 제공하지 않기 때문에 배열을 사용하여 큐인척해야 하는데, push()와 shift() 메서드를 사용하면 런타임을 초과하는 것이었다.

대킴님이 종종 하시는 말씀이 있다. "shift()와 unshift()는 효율이 썩 좋지는 않다. 배열의 맨 앞 값을 다루기 때문이다. c++ 할 때 배웠다!"라는 것이다. 때문에 그동안 shift() 메서드를 자주 사용하지는 않았다.

하지만 큐가 없는 자바스크립트에서 큐를 사용해야 하는 지금, 대체 어쩌라고~~~!!!!!!!싶었지만.... 투 포인터라는 좋은 방법이 있었다!

투 포인터

두 큐를 합친 다음, 큐 하나의 시작점과 끝점을 정해놓고 각 포인터를 이동시키면서 큐인 척 계산하는 방법이다. 아래는 투포인터를 사용하여 풀어본 식이다.

function solution(queue1, queue2) {
    const queue = queue1.concat(queue2);
    const goal = queue.reduce((a, b) => a + b) / 2;
    
    let [start, end] = [0, queue1.length];
    let sum = queue1.reduce((a, b) => a + b);
    
    for (let move = 0; move <= queue.length; move++) {
        if (sum === goal) return move;
        if (sum > goal) {
            sum -= queue[start];
            start++;
        }
        else {
            sum += queue[end];
            end++;
        }
    }
    return -1;
}

큐의 최댓값을 구하는 조건문은 타임아웃이 나서 삭제했다.

위의 식으로 실행했더니 테스트 1번만 통과가 안됐다. 혹시나 하는 마음으로 반복문 탈출 조건을 조금씩 늘려봤더니, queue.length + 2 부터는 통과가 되더라...ㅎ 최악의 경우를 잘못 생각한 것 같아서 내일 스터디 때 함께 의논해 보고 아래에 추가로 적어놓겠다.

+) 최악의 경우

아래의 예시는 자배가 생각해본 최악의 경우다.

// 들어오는 인자
const queue1 = [1, 10, 1, 2];
const queue2 = [1, 2, 1, 2];

// 이동 결과(이동 횟수 7)
const queue1 = [1, 2, 1, 2, 1, 2, 1];
const queue2 = [10];

하지만 지금 쓰면서 생각해보니 더 최악의 경우가 있다.

// 들어오는 인자
const queue1 = [1, 1, 10, 2];
const queue2 = [1, 2, 1, 2];

// 이동 결과(이동 횟수 9)
const queue1 = [2, 1, 2, 1, 2, 1, 1];
const queue2 = [10];

이 경우 내가 풀었던 식대로 하면 두 배열을 붙여서 만든 queue는 다음과 같은 모양이 된다.

const queue = queue1.concat(queue2);

console.log(queue);	// [1, 1, 10, 2, 1, 2, 1, 2]

이 때의 [start, end]는 최종적으로 [2, 7]에서 머물게 된다. queue[0], queue[1]의 값을 합치지 못하는 것이다. 때문에 end가 마지막 인덱스에 도달했을 때의 조건문을 추가해줬다.

function solution(queue1, queue2) {
    const queue = queue1.concat(queue2);
    const goal = queue.reduce((a, b) => a + b) / 2;
    
    let [start, end] = [0, queue1.length];
    let sum = queue1.reduce((a, b) => a + b);
    
    for (let move = 0; move < queue1.length * 3; move++) {
        if (sum === goal) return move;
        if (sum > goal) {
            sum -= queue[start];
            start++;
        }
        else {
            sum += queue[end];
            end++;
            if (end >= queue.length) end = 0;
        	// 마지막 인덱스에 도달한 경우 맨 앞으로 이동
        }
    }
    return -1;
}

최종적으로 수정한 코드는 이렇다!!! 다음엔 더 꼼꼼하게 생각하기~~!!!