[투포인터] 프로그래머스 '두 큐 합 같게 만들기' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/118667#qna

프로그래머스

2. 코드

처음 푼 코드) 당연한 타임아웃

function solution(queue1, queue2) {
    let answer = 0;
    // 두 큐 요소 합 구하기
    // 두 큐 중 합 큰 것에서 하나 빼서 옮기기
    queue1 = queue1.reverse();
    queue2 = queue2.reverse();
    let sum1 = queue1.reduce((acc,cur) => acc += cur,0);
    let sum2 = queue2.reduce((acc,cur) => acc += cur,0);
    if((sum1+sum2)/2 !== Math.floor((sum1+sum2)/2)) return -1;
    
    while(sum1 !== (sum1+sum2)/2){
        if(!sum1 || !sum2 || (sum1+sum2)/2 !== Math.floor((sum1+sum2)/2)) return -1;
        if(sum1 > sum2) queue2.unshift(queue1.pop());
        else queue1.unshift(queue2.pop());
        sum1 = queue1.reduce((acc,cur) => acc += cur,0);
        sum2 = queue2.reduce((acc,cur) => acc += cur,0);
        answer ++;
    }
    
    return answer;
}

정답 코드)

이 문제는 문제 그대로 보고 큐로 해야겠네~ 이러면 타임아웃 지옥에 빠지게 된다. 

투포인터를 사용하여 두 개의 큐를 하나로 합치고, 포인터를 두어 앞뒤로 왔다갔다하며 비교하도록 해야한다.

두 큐의 길이가 같으므로, qPointer1은 0번부터 최대 기존 queue1 길이의 2배만큼, qPointer2는 큐 길이에 해당하는 인덱스 부터  큐 길이에 해당하는 인덱스 * 2까지 갈 수 있으므로 최대 큐 길이 * 3만큼 이동할 수 있어, 이동 횟수의 최대값은 큐 길이 * 3이 된다.

const solution = (queue1, queue2) => {
  const newQ = [...queue1, ...queue2];
  let sum1 = queue1.reduce((prev, cur) => prev + cur, 0);
  let sum2 = queue2.reduce((prev, cur) => prev + cur, 0);
  const half = (sum1 + sum2) / 2;
  let q1P = 0;
  let q2P = queue1.length;

  for (let cnt = 0; cnt < queue1.length * 3; cnt++) {
    if (sum1 === half) {
      return cnt;
    }
    sum1 = sum1 > half ? 
           sum1 - newQ[q1P++ % newQ.length] : sum1 + newQ[q2P++ % newQ.length];
  }

  return -1;
};

 

이해에 도움이 된 블로그)

https://koguri.tistory.com/108

[프로그래머스] 두 큐 합 같게 만들기(javascript)

 

복기

6/23