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

문제 링크

프로그래머스

 

문제 유형

큐, 투 포인터

 

문제 풀이

해당 문제는 두 큐가 주어지고, 각 큐의 총합이 같게 나오도록 pop과 insert한 횟수를 반환하는 문제이다. 처음에 pop과 push를 사용해 두 큐의 요소들을 이동시켰다. 하지만 이는 너무 많은 push, pop 연산이 일어나 다른 방법을 찾아보았다. 처음에는 각 큐에 투 포인터를 두고 요소를 넣고 빼고 해볼까 생각했지만 구현이 어려웠다. 그러다 두개의 큐를 합친 후 투 포인터를 사용하는 접근법 힌트를 얻고 문제를 구현할 수 있었다.
두 큐를 합친 후 하나의 큐 범위에 시작, 끝 포인터를 두고 target 값보다 작으면 queue2의 첫번째 원소를 가져오기 위해 end 포인터를 1 증가시킨다. 하나의 큐의 합이 target보다 크면 queue1의 첫번째 원소를 제거하기 위해 start 포인터를 1 증가시킨다.

 

코드

function solution(queue1, queue2) {
    const queue = queue1.concat(queue2);
    const target = queue.reduce((arr, cur) => arr + cur) / 2;
    
    let sum1 = queue1.reduce((arr, cur) => arr + cur);
    let start = 0, end = queue1.length - 1, count = 0;
    
    while (start < queue.length && end < queue.length) {
        if (sum1 === target) return count;
        else if (sum1 < target && end < queue.length) {
            end++;
            sum1 += queue[end];
        }
        else {
            sum1 -= queue[start];
            start++;
        }
        count++;
    }
    return -1;
}