[Programmers] (2022 KAKAO TECH INTERNSHIP) Lv 2. 두 큐 합 같게 만들기

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

프로그래머스

 

const sumFunc = (arr) => arr.reduce((acc, cur) => acc + cur, 0);

function solution(queue1, queue2) {
    let [answer, sum1, sum2, idx1, idx2] = [0, sumFunc(queue1), sumFunc(queue2), 0, 0];
    const [half, limit] = [(sum1 + sum2) / 2, queue1.length * 3];

    // shift 없이 idx를 사용하는 이유는 js는 queue를 지원하지 않기 때문에
    // shift를 사용하면 시간복잡도(n)이 걸려서 시간초과가 날 수 있다.
    
    // limit는 최악의 케이스를 대비한 수.
    // 최악의 케이스는 한 큐에서 하나를 제외하고, 다른 큐로 모두 보내는 경우이기 때문에
    // 원래 길이 * 3을 넘어서 순회할 경우 return해서 탈출하도록 설정.
    
    while (answer < limit) {
        if (sum1 === sum2)
            break;

        if (sum1 > half) {
            const data = queue1[idx1++];
            sum1 -= data, sum2 += data, queue2.push(data);
        } else {
            const data = queue2[idx2++];
            sum1 += data, sum2 -= data, queue1.push(data);
        }
        ++answer;
    }

    return (answer < limit) ? answer : -1;
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/118667.%E2%80%85%EB%91%90%E2%80%85%ED%81%90%E2%80%85%ED%95%A9%E2%80%85%EA%B0%99%EA%B2%8C%E2%80%85%EB%A7%8C%EB%93%A4%EA%B8%B0

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드