(프로그래머스 KAKAO JS)두 큐 합 같게 만들기

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

프로그래머스

큐 자료구조를 만들어서 사용하여 시간초과가 나지 않도록 한다.

sum1 = queue1의 원소의 합

sum2 = queue2의 원소의 합

 

우선 두 큐를 직접 정의한 큐에 넣으면서, 각 큐의 총합을 구한다.

두 합이 짝수가 아니라면 -1 리턴,

만약 두 합이 같다면 0을 리턴한다.

 

이후는 while문을 이용해 두 큐의 합이 같아질 때까지 반복한다.

만약 현재까지의 연산 횟수 answer가 두 큐의 사이즈 + 2보다 크다면 더 이상 진행이 불가능하기 때문에 -1을 리턴하여 종료한다.

그렇지 않다면 sum1과 sum2가 같아질 때까지 연산을 수행한다.

 

연산의 원리는 sum1과 sum2를 비교하여 합이 더 큰 큐에서 작은 큐로 옮기는 것이다.

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }

    push(value) {
        this.queue[this.rear++] = value;
    }

    pop() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front++;
        return value;
    }

    size() {
        return this.rear - this.front;
    }
}

function solution(queue1, queue2) {
    const len = queue1.length;
    const q1 = new Queue();
    const q2 = new Queue();
    let answer = 0;
    let sum1 = 0;
    let sum2 = 0;
    
    for(let i = 0; i < len; i++){
        sum1 += queue1[i];
        sum2 += queue2[i];
        
        q1.push(queue1[i]);
        q2.push(queue2[i]);
    }
    
    if((sum1 + sum2) % 2){
        return -1;
    } if(sum1 === sum2){
        return 0;
    }
    
    while(1){
        if(answer > q1.size() + q2.size() + 2){
            return -1;
        }
        
        if(sum1 < sum2){
            const pop = q2.pop();
            
            sum1 += pop;
            sum2 -= pop;
            q1.push(pop);
        } else if(sum2 < sum1){
            const pop = q1.pop();
            
            sum1 -= pop;
            sum2 += pop;
            q2.push(pop);
        } else if(sum1 === sum2){
            break;
        }
        
        answer++;
    }
    
    return answer;
}