[프로그래머스][슬라이딩 윈도우] 두 큐 합 같게 만들기

     

목차

 

문제

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

프로그래머스

 

 

문제 구현 방향

두 개의 큐를 이어 붙인다고 생각하고 슬라이딩 윈도우처럼 한번 순회한다고 생각하면 편하다.

또한 큐가 서로 번갈아가며 생기는 경우가 생기는데 이때는 두 큐의 길이 합이상을 순회시킨 이후에도 돌면 break를 걸어주어야 한다. 모든 조건을 탐색해보았기 때문이다. 

 

-> js의 경우 큐를 직접 구현해야 시간 초과가 발생하지 않는다. (shift의 경우 O(n)이기 때문이다.)

-> 숫자의 범위가 굉장히 크므로 BigInt를 써주었다.

 

코드 구현

class queue{
    constructor(){
        this.m = new Map();
        this.rear = 0;
        this.front =0;
    }
    size(){
        return this.m.size;
    }
    add(value){
        this.m.set(this.rear, value);
        this.rear++;
    }
    pop(){
        if(this.m.size === 0)return undefined;
        let t = this.m.get(this.front);
        this.m.delete(this.front);
        this.front++;
        if(this.m.size === 0){
            this.front =0;
            this.rear =0;
        }
        return t;
    }
    
}


function solution(queue1, queue2) {
        
    var answer = 0;
    let limit = queue1.length*2+3;
    let q1 = new queue();
    let q2 = new queue();

    let sum1 = 0n;
    let sum2 = 0n;
    for(let i=0; i<queue1.length; i++){
        q1.add(BigInt(queue1[i]));
        q2.add(BigInt(queue2[i]));
        sum1 += BigInt(queue1[i]); 
        sum2 += BigInt(queue2[i]);
    }
    
    let half = (sum1+sum2)/2n;

    while(q1.size() && q2.size()){
        if(answer > limit)
            break;
        if(sum1 === half && sum2 === half)
            return answer;
        if(sum1 < sum2){
            let p = q2.pop();
            q1.add(p);
            sum1 += p;
            sum2 -= p;
        }else{
            let p = q1.pop();
            q2.add(p);
            sum2 += p;
            sum1 -= p;
        }
        answer++;
    }

    return -1;
}