문제

문제 링크: 2022 KAKAO TECH INTERNSHIP: 두 큐 합 같게 만들기

풀이 시간: 01:15

두개의 큐가 [1,2,3,4][5,6,7,8]이 존재한다고 가정한다.
pop, push 두개의 과정을 1회 연산이라고 한다.
두 큐의 합을 같게 만들려면 몇번의 연산을 거쳐야 하는가?

풀이 시도

제일 처음에 두개의 큐 앞 뒤가 서로 연결되어 있다고 생각 했습니다.
그래서 큐 두개를 하나의 배열로 만든 후에 투 포인터를 사용해서 합이 절반이 되는 지점을 찾았습니다.
그 후에 시작 index, 끝 index를 가지고서 아래 코드처럼 연산 횟수를 구했습니다.

아, 그리고 큐를 두개를 붙이면 큐의 시작 인덱스가 더 큰 경우는 처리를 못해줘서 큐1, 큐2, 큐1 이런식으로 큐를 붙여줬습니다.

function calcCount(startIdx, endIdx, halfIdx) {
  let result = 0;

  if (startIdx < halfIdx && endIdx < halfIdx) {
    result += endIdx - halfIdx;
  }
  if (startIdx > halfIdx) result += halfIdx;
  else result += startIdx - 1;

  if (startIdx > halfIdx) result += startIdx - 1 - halfIdx;

  if (endIdx > halfIdx) result += endIdx - halfIdx;

  return result;
}

그런데 이렇게 하나하나 조건을 따져가면서 문제를 풀었더니 반례가 생겼습니다.
그런데 도저히 해결할 방법이 떠오르지 않아서 조금 다르게 생각을 해 봤습니다.

정답 풀이

원래 생각했던 방법은 연산횟수를 계산하기 위한 용도로 중간값을 찾아줬습니다.
그래서 반례도 많이 생기고 땜빵하듯이 코드를 작성 해 나가게 됐습니다.
투포인터를 사용하면서 연산회수를 계산할 방법이 없을까? 하다가
처음부터 양쪽 큐의 합이 같다고 가정을 하고 시작 해 봤습니다.

그러면 0회로 가정할 수 있게 되고, 거기서 뒤로 넣거나 앞으로 넣는 동작을 한다고 생각하면 됩니다.
즉, 투 포인터로 인덱스가 바뀔 때 마다 연산횟수를 늘리면 됐습니다.

그렇게 아래처럼 문제를 풀게 되었습니다.

function solution(queue1, queue2) {
  const getSum = (arr) => arr.reduce((acc, cur) => acc + cur, 0);

  const arr = [...queue1, ...queue2, ...queue1, ...queue2];
  const half = getSum(arr) / 4;

  let [left, right] = [0, queue1.length];
  let sum = getSum(queue1);
  let cnt = 0;

  for (let i = 0; i < queue1.length * 3; i++) {
    if (sum > half) sum -= arr[left++];
    else if (sum < half) sum += arr[right++];
    else return cnt;

    cnt++;
  }
  return -1;
}