프로그래머스 두 큐 합 같게 만들기 [JS]

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

프로그래머스

 

문제

간단히 말해서, 두 개의 큐를 조절해서 각 큐의 요소들의 합이 같게 만드는 문제. 

 

입력

---

문제 해설

오랜만의 문제 풀이라 그런지 많이 풀이를 생각해 내는 것이 꽤 어려워서.. 풀이를 보고 풀었습니다.

 

1. queue 1의 합만 체크해서 queue1의 합이 목표 숫자 (총합 /2) 보다 작으면 다른 큐에서 받아오고, 크면 다른 큐로 내보낸다.

2. 최대 이동 횟수는 모든 원소 개수의 합 보다 낮다. (근데 완전 빡빡하게 하니,, 틀려서 +5 하니 맞았습니다.)

 

하지만 시간초과가 나서 의아했는데...

 

 

네,,, js의 shift는 배열이라서 당기는 시간이 필요해서 시간복잡도가 O(n)입니다.

앞으로도 혹시 shift 연산이 필요한 경우에는 python을 선택하거나, js가 고정인 경우에는 인덱스를 활용한 풀이를 해야겠습니다.

아래는 최종 코드입니다.

 

function solution(queue1, queue2) {
    var answer = -1;
    let maxMove = queue1.length + queue2.length;
    let curtMove = 0;
    let count1 = 0;
    let count2 = 0;
    
    for ( let q of queue1) {
        count1 += q;
    }
    for (let q of queue2) {
        count2 += q;
    }
    const target = (count1 + count2)/2
    if((count1 + count2)%2 || (queue1.length + queue2.length) %2) return -1;
    
    let queue1_idx = 0;
    let queue2_idx = 0;

    while(curtMove < maxMove +5){
        if(count1 == target) {
            return curtMove;
        }
        else if (count1 < target) {
            count1 +=  queue2[queue2_idx];
            queue1.push(queue2[queue2_idx]);
            queue2_idx+=1;
        }
        else {
            count1 -=  queue1[queue1_idx];
            queue2.push(queue1[queue1_idx]);
            queue1_idx += 1;
        }
        curtMove++;
    }
    return answer;
}