프로그래머스 level 2 - 두 큐 합 같게 만들기(Javascript)

두 큐 합 같게 만들기

배운 것, 유의할 것

시간초과와의 싸움(했다치고!)

문제 해결 방법을 찾는 것은 전혀 어려움이 없었다. 하지만 제한사항이 아래와 같아서 시간초과 등의 문제가 있을 것이 분명하긴 했다.

제한사항
1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
1 ≤ queue1의 원소, queue2의 원소 ≤ 109

이런 저런 시도를 해본결과 정답케이스를 늘릴 수는 있었지만 모두 해결할 수 없어서 다른 분의 풀이를 보고 참고했다. 시간초과를 줄이기 위해 개선한 부분을 일부 적어보면,

// 1. 큐 배열의 합계 업데이트 방식
// 매 반복에서 queue1과 queue2의 합을 업데이트 해주는 부분
// 최초에는 매 반복마다 추출과 삽입 이후 reduce를 써서 q1Sum과 q2Sum을 업데이트 해주었음
q1Sum = queue1.reduce((acc,cur)=>acc + cur,0);
q2Sum = queue2.reduce((acc,cur)=>acc + cur,0);
// 이를 교환되는 값만큼만 줄고 늘도록 개선
// q1Sum이 q2Sum보다 클 때, 반대의 경우 부호 반대
	...
	if(q1Sum > q2Sum){
		const item = queue1[idx1++]
		q1Sum -= item;
		q2Sum += item;
		queue2.push(item);
	} else if(q1Sum < q2Sum){
	...

// 2. shift() 사용 최소화를 위해 index 사용
// O(n)의 시간복잡도를 갖는 shift() 사용을 index로 대체해서 q1Sum, q2Sum에 증감되는 값만 반영해주는 방식으로 처리했다.

실제 큐를 출력해보면 shift() 처리가 안되어있기 때문에 다른 큐에 삽입한 원소들이 그대로 남아있다. 다만 우리는 큐의 동작방식을 알기 때문에 배열의 합계에는 이를 반영해주었고, 인덱스만 늘린다면 두 배열의 합계 값에 따라 큐별로 어떤 인덱스의 원소를 처리해줘야하는지 알고 있기 때문에 가능한 방법이다.

정답코드

function solution(queue1, queue2) {
    // 두 큐의 합, 교환을 반복하며 업데이트 필요
    let q1Sum = queue1.reduce((acc,cur)=>acc + cur,0);
    let q2Sum = queue2.reduce((acc,cur)=>acc + cur,0);
    let qLen = queue1.length + queue2.length
    // shift를 대체하기 위해 인덱스 사용
    let idx1 = 0, idx2 = 0;
    // 몇 번의 교환이 이뤄지는지 체크할 변수
    let count = 0;
    while(count < qLen * 2){
        if(q1Sum > q2Sum){
            const item = queue1[idx1++]
            q1Sum -= item;
            q2Sum += item;
            queue2.push(item);
        } else if(q1Sum < q2Sum){
            const item = queue2[idx2++]
            q1Sum += item;
            q2Sum -= item;
            queue1.push(item);
        } else {
            return count
        }
        count++;
    }
    return -1;
}