[프로그래머스 lev2/JS] 두 큐 합 같게 만들기

문제 출처

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

나의 풀이

재귀를 돌려고 하면 크기도 크고, 분기점을 나누기도 애매하다.
왼4오4 => 왼5오3 => 왼6오2 => 왼7오1
71에서 다시 원복해서 찾아 갈 또 다른 경우의 수가 없다.

경우의 수를
(1)왼쪽에서 빼서 오른쪽에 넣거나
(2)오른쪽에서 빼서 왼쪽에 넣거나
로 나눠보려 했으나 생각해보니 문제에서 요구하는 논리와 맞지 않는다.
[ 3, 2, 7, 2 ], [ 4, 6, 5, 1 ]
[ 3, 2, 7, 2, 4], [6, 5, 1 ]
[ 3, 2, 7, 2, 4, 6], [5, 1 ]
[ 3, 2, 7, 2, 4, 6, 5], [1]
에서
[ 2, 7, 2, 4, 6, 5], [3, 1]
다시 왼쪽에서 뺀 걸 오른쪽으로 넣게 되므로 이 지점에서 문제가 생기는 것 같다.
[ 2, 7, 2, 4, 6, 5, 3], [1]

되도록이면 배열을 건드리지 않아야 순서가 꼬이지 않을 것 같다.
하지만 방법이 떠오르지 않는다..

다른 풀이

가장 먼저 판단해야 할 것 중 하나는 완전탐색을 해야 하는지 아닌지이다.

큐의 합이 더 작으면 굳이 더 들어갈 필요가 없으므로, 완전탐색은 매우 비효율적이다 ⇒ 투포인터, 그리디

(totalNum < goalNum) 인 순간 더 이상 탐색하는 게 의미가 없으므로, 이때 += 해준다. 반대 상황도 마찬가지이다.

function solution(queue1, queue2) {
  let totalArr = [...queue1, ...queue2];
  let maxCount = totalArr.length*2;
  let start = 0;
  let end = queue1.length;
  
  const sum = (arr)=>arr.reduce((a,b)=>a+b);
  let totalNum = sum(totalArr.slice(start, end));
  let goalNum = sum(totalArr)/2;
  let count = 0;

  console.log(totalNum, goalNum);
  
  while(count <= maxCount){
      if(totalNum < goalNum){
          totalNum += totalArr[end];
          end++;
      }else if(totalNum > goalNum){
          totalNum -= totalArr[start];
          start++;
      }else if(totalNum === goalNum){
          return count; 
      }
      count++;
  }
  
  return -1;
}

console.log(solution([3, 2, 7, 2], [4, 6, 5, 1]));