2Level / 2022 KAKAO TECH INTERNSHIP / 두 큐 합 같게 만들기

문제 설명

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

프로그래머스

 

풀이 방법

이번 문제는 큐를 이어붙여 투포인터 알고리즘을 이용해 풀었다.

시작포인터와 끝 포인터는 각각 0과 첫번째 큐의 끝으로 설정해 두었다.

그 이유는 한개의 큐의 합이 전체 큐의 합의 절반이 되는 것을 감지해야하기 때문에 첫번째 큐의 합을 기준으로 크다면 lp에 해당하는 수를 빼고, 작다면 rp에 해당하는 수를 더해주면서 문제를 풀었다.

 

코드

const solution = (queue1, queue2) => {
    let queue = [...queue1, ...queue2];
    let sum1 = queue1.reduce((a, c) => a + c, 0);
    let target = queue.reduce((a, c) => a + c, 0) / 2;
    let lp = 0, rp = queue1.length-1;
    
    for(let cnt = 0; cnt < queue1.length * 3; cnt++){
        if(sum1 === target){
            return cnt;
        }
        if(sum1 < target){
            sum1 += queue[++rp];
        }
        else{
            sum1 -= queue[lp++];
        }
    }
    return -1;
}