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

 

출처

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

프로그래머스

 

문제

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 

 

각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

 

제한사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 10 ^ 9
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

풀이

배열로 큐를 구현하려 시도하니, 너무 많은 메서드 사용과, 연산으로 인해 시간 초과가 발생했습니다.

 

이럴 때 사용한 방법으로 알고리즘 문제에 자주 등장하는 투 포인터(다중 포인터) 알고리즘 방식을 사용하면 다른 원소를 가리키는 다중의 포인터를 조작하면서 원하는 값을 얻을 수 있습니다.

 

해당 방식을 사용하여 구현하게 되면, 실제로 배열에서 값을 빼고, 넣는 것이 아니기에 불필요한 연산이 줄어들게 됩니다.

 

최대 반복 횟수(queue1 길이 * 3) 만큼 돌려주면서, 한쪽 큐의 총합이 목표치보다 높을 시에는 queue1의 pointer 값를 높여주고, 값이 작으면 queue2의 pointer 값을 높여주면서 해당 값을 빼고, 넣는 효과를 통해 총합의 값을 조절해줍니다.

 

코드

function solution(queue1, queue2) {
    let sumQ1 = sum(queue1),
        sumQ2 = sum(queue2);
    
    let pointer1 = 0, 
        pointer2 = queue1.length;
    
    const target = (sumQ1 + sumQ2) / 2;
    const queue = [...queue1, ...queue2];
    
    const end = queue1.length * 3;
    
    for (let count = 0; count < end; count++) {
        if (sumQ1 === target) {
            return count;
        }
        
        if (sumQ1 > target) {
            sumQ1 -= queue[pointer1++];
        } else {
            sumQ1 += queue[pointer2++];
        }
    }
    
    return -1;
}

const sum = (arr) => arr.reduce((acc, v) => acc + v, 0);