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

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(queue1, queue2) {
    class Node {
        constructor(value) {
            this.value = value;
            this.next = null;
        }
    }
    
    class Queue {
        constructor(arr) {
            this.head = null;
            this.tail = null;
            this.sum = 0;
            arr.forEach(elem => this.insert(new Node(elem)));
        }
        
        insert(node) {
            if (!this.head) {
                this.head = node;
            } else {
                this.tail.next = node;
            }
            this.tail = node;
            this.sum += node.value;
        }
        
        pop() {
            if (!this.head) {
                return null;
            }
            if (!this.head.next) {
                this.tail = null;
            }
            const output = this.head;
            this.head = this.head.next;
            this.sum -= output.value;
            return output;
        }
    }
    
    const length = queue1.length;
    const queueA = new Queue(queue1);
    const queueB = new Queue(queue2);
    
    let result = 0;
    let isPossible = false;
    while (result < length * 4) {
        if (queueA.sum > queueB.sum) {
            const node = queueA.pop();
            queueB.insert(node);
        } else if (queueA.sum < queueB.sum) {
            const node = queueB.pop();
            queueA.insert(node);
        } else {
            isPossible = true;
            break;
        }
        result++;
    }
    
    return isPossible ? result : -1;
}

직접 큐를 구현하고, queue1과 queue2의 합을 비교하여 더 큰 쪽에서 원소를 pop하여 더 작은 쪽으로 insert하면서 합이 같아질 때까지 반복한다. 합이 같아지면 result를 구할 수 있고, 합이 같아지지 않는다면 무한 반복이 될 수 있기 때문에 조건으로 result가 특정 횟수 이상을 넘어가지 못하면 -1을 반환하도록 하였다.

 

그런데 이 문제 관련 풀이나 질문글을 찾아봐도 "특정 횟수"가 정확히 몇인지를 명쾌하게 소개한 글을 찾지 못하였다.

(length * 3으로 통과한 분들이 많다. 2.5도 넣어봤는데 통과가 된다.)

혹시 아시는 분은 댓글로 알려주시면 감사하겠습니다.