77.md

두 큐 합 같게 만들기

설레었냐? 아직은 아니야... 한 번에 통과할뻔했던 꿈

Try1

function solution(queue1, queue2) {
  const total = queue1.concat(queue2).reduce((acc, cur) => acc + cur, 0);
  const target = total / 2;

  let q1Sum = queue1.reduce((acc, cur) => acc + cur, 0);
  let count = 0;

  if (!Number.isInteger(target)) return -1;

  while (q1Sum !== target) {
    if (queue1.length === 0 || queue2.length === 0) return -1;
    if (q1Sum < target) {
      const shifted = queue2.shift();
      queue1.push(shifted);
      q1Sum += shifted;
    } else {
      const shifted = queue1.shift();
      queue2.push(shifted);
      q1Sum -= shifted;
    }
    count++;
  }

  return count;
}

위 문제는 표면적으로, 명시적으로 큐의 pop과 insert를 통해서 두 큐의 합을 같게 만드는데 걸리는 횟수를 요구한다. 나는 당연하게도 큐(자바스크립트에서는 배열을 통해서 구현)를 이용해서 문제를 풀어내었다. 로직은 구해야할 (균형)합을 구하고 합보다 크면 shift 해주고 합보다 작으면 push해주는 방식으로 구현했다. 이 문제를 풀면서 습관처럼 살펴보면 시간복잡도, 시간초과에 대해선 크게 신경쓰지 않았던 것 같다. 오랜만에 한 번의 제출로 테스트케이스에서 연속적인 파란불이 들어왔다. 그러다가 80%정도 통과하고 나머지는 시간초과가 떴다. 그래도 뭔가 한번에 많은 테스트 케이스를 통과했다는 기쁨이 있었다.

시간초과

해당 문제의 시간초과에 대해서 찾아보니 shift 메소드 자체의 시간복잡도가 O(n)이기때문에 위 코드는 O(n^2)이 되기때문에 최악의 경우, 300000 * 300000이 될 수 있다. 그래서 큐를 직접적으로 이용하는 바업ㅂ이 아닌 다른 방법을 생각해봐야했다.

Try2

결국 이 문제는 투포인터 문제였다.

function solution(queue1, queue2) {
  const concated = queue1.concat(queue2);
  const total = concated.reduce((acc, cur) => acc + cur, 0);
  const target = total / 2;

  let q1Sum = queue1.reduce((acc, cur) => acc + cur, 0);
  let count = 0;
  let left = 0,
    right = queue1.length;

  if (!Number.isInteger(target)) return -1;

  while (q1Sum !== target) {
    if (left >= right) return -1;
    if (left > concated.length - 2) return -1;

    if (q1Sum < target) {
      q1Sum += concated[right];
      right++;
    } else {
      q1Sum -= concated[left];
      left++;
    }
    count++;
  }

  return count;
}

내가 생각하는 몇가지 포인트에 대해서 설명하면 이렇다.

1. 하나의 큐에서 체크해야 할, 가능한 경우의 수가 정해져있다.

   4개의 요소로 이루어진 배열 2개라면, 총 8개로 이루어진 배열이라고 가정하면, 1개의 요소부터 7개의 요소를 더한 것까지 중에서 target(균형합)이 있는지를 체크한다. 그 중에서 나오지 않는다면, 두 개의 큐의 요소로는 같은 합을 만들 수 없는 것이 된다. (7개인 이유는 하나의 큐에는 적어도 1개의 요소가 들어있어야하기 때문에...)

2. 큐의 직접적인 동작(pop, insert)를 하지 않더라도 투포인터의 left와 right를 옮기는 행위가 문제에서 요구한 한 번의 동작(한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것)을 포함하게 된다.

큐라는 탈을 쓴 투포인터 문제였던 것이다. 역시 문제가 잘 풀리면, 함정(?)이 존재하는법.