[JS] 두 큐 합 같게 만들기

 

난이도: Lv. 2

정답률: 53%

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

프로그래머스

 

 

알고리즘

정해진 루프 카운트 동안 총합이 큰 큐에서 작은 큐 쪽으로 원소를 넘겨주는 과정을 반복한다.

이 문제에서 중요한 것은 최대 루프 카운트를 얼마로 할 것인가이다. 최대 경우의 수는 원소가 원래 자리로 돌아오는 것으로, 그림으로 표현하면 다음과 같다.

큐2를 처음과 같은 상태로 만들지 않았음에도 끝내는 이유는 다음과 같다.

빨간 배경인 상황들을 보자. 이 문제를 푸는 데에 있어서 두 상황은 유의미한 차이가 없다. 원소가 원래 자리로 돌아오기까지 3n + 1번의 작업을 수행했다.

이후에 큐1의 원소들을 다시 큐2로 집어넣는다고 해보자. 들어가 있는 큐는 반대지만 언젠가 한 번은 일어났던 상황이다.

따라서 3n + 1 번의 작업부터 발생하는 모든 상황은 이미 언젠가 발생했던 상황이기 때문에 최대 루프 카운트는 3n이다.

 

 

코드

최대 루프 카운트는 3n이지만 두 큐의 합이 같은지 판별하는 코드가 반복문의 맨 위에 있어서 최대 루프 카운트를 3n + 1로 설정했다.

function solution(queue1, queue2) {
    let answer = 0;
    let loopCount = 0;
    const endCount = queue1.length * 3 + 1;

    let q1StartIdx = 0;
    let q2StartIdx = 0;

    let sumQ1 = queue1.reduce((acc, curr) => acc + curr);
    let sumQ2 = queue2.reduce((acc, curr) => acc + curr);
    if ((sumQ1 + sumQ2) % 2 === 1) { return -1; }

    while (loopCount <= endCount) {
        if (sumQ1 === sumQ2) {
            return answer;
        } else if (sumQ1 > sumQ2) {
            const popElement = queue1[q1StartIdx];
            queue2.push(popElement);
            sumQ1 -= popElement;
            sumQ2 += popElement;
            q1StartIdx++;
        } else {
            const popElement = queue2[q2StartIdx];
            queue1.push(popElement);
            sumQ1 += popElement;
            sumQ2 -= popElement;
            q2StartIdx++;
        }

        answer++;
        loopCount++;
    }
    
    return -1;
}

 

 

주저리

고난1

테케1이 계속 실패했다. shift 쓰면 안 되는 거 같아서 shift 안 하고 배열 잘라서 한 번에 push 하는 코드를 짰었는데 그건 통과되던데 시간이 박살 나서 갖다 버렸다. 질문하기 뒤지다가 최대 순회 가능 횟수가 잘못됐다는 걸 알긴 했는데 도저히 이해가 안 돼서 환형 큐로 설명하는 블로그 글을 봤는데 진짜 꼴도 보기 싫어서 바로 끄고 노트에 그냥 큐 그려놓고 끄적이다가 깨달았다. ppt로 그림 만들다가 어라 근데 큐 전체를 원상태로 되돌려야 하는 거 아닌가? 하는 생각이 들었는데 어째 저째 저 생각이 떠올라서 해결했다.

 

고난2

테케 3개가 시간초과 나는 문제를 해결해야 했다. 사실 shift 때문이라는 건 알고 있었다. 배열 잘라서 다시 할당하는 걸로 해결해보려고도 했는데 이게 더 오래 걸렸다. 시간초과 문제를 해결하는 게 우선이라서 공간 복잡도는 모른척하고 푸는 방법을 선택했다.