두 큐 합 같게 만들기

Kakao Tech Internship 문제

생각보다 간단하다고 생각했는데 막상 풀어보니 시간복잡도에서 막혔던문제였다. 30개중에 3개의 테스트케이스에서 시간초과가 발생..

원인은 queue를 구현할때 자주 쓰는 shift() 메서드였는데 조건으로 주어진 배열 길이가 300,000이 넘어가면서 배열의 길이만큼의 for루프 내부에 각 원소마다 shift()를 사용하면서 전체적으로 O(N^2)만큼의 단계가 걸리게 되어 시간초과가 뜨는거였다.

shift() 메서드를 대신해서 slice, 구조분해할당 등의 방법을 시도해봤지만 해결되지않았고
구글링 해보니 start, end 포인터로 배열의 위치를 지정해서 푸는 방법이 있었다.

배열의 마지막에 삽입, 삭제하는 push(), pop()은 O(1)의 시간복잡도,
배열의 처음에 삽입, 삭제하는 unshift()와 shift()는 O(N)의 시간복잡도를 가진다.

1. 두 큐를 concatQueue 하나의 배열로 합친다.

2. 첫 시작에 queue1은 0인덱스부터 queue1.length 인덱스 전까지 이다.
   (start = 0, end = queue1.length)

3. 목표값을 설정한다. (queue1 원소의합 + queue2 원소의합) / 2

4. concatQueue의 start~end 인덱스까지 합(totalSum)을 기준으로 목표값과 비교한다.

5. totalSum 이 목표값보다 크다면
   => queue1의 원소합이 크기때문에 queue1에서 queue2로 원소를 넘긴다. totalSum에서 concatQueue[start] 값을 빼주고 start 포인터를 옮긴다.

6. totalSum 이 목표값보다 작다면
   => queue2의 원소합이 크기때문에 queue2에서 queue1로 원소를 넘긴다. totalSum에 concatQueue[end] 값을 더해주고, end 포인터를 옮긴다.

7. 위의 작업은 (target === totalSum) 조건 시 count를 반환하기 전까지 반복하는데 반복문이 끝날때까지 조건에 걸리지 않으면 두 큐는 같게 만들 수 없는 배열이다.
   => for문의 최대 반복횟수는 (초기 queue1.length -1)*3 까지이다. 마지막에 목표값과 totalSum이 같은지 확인하기때문에 <= 일때까지 반복한다.

test case)
[1,2][4,1] => for문 4번필요 (4를 넘기고 1,2를 받는다 + 마지막 확인)
[1,2,1][1,6,1] => for문 7번 필요 (1,6을 넘기고 1,2,1,1을 받는다 + 마지막 확인)
[1, 2, 1, 2][1, 1, 10, 2] => for문 10번 필요

function solution(queue1, queue2) {
    let count = 0;
    let start = 0;
    let end = queue1.length;
    
    const concatQueue = [...queue1, ...queue2];
    const queueLen = queue1.length;
    
    const getSum = (arr) => arr.reduce((acc, cur) => acc + cur);
    
    const sumQueue1 = getSum(queue1);
    const sumQueue2 = getSum(queue2);
    
    // 예외사항 처음부터 합이 같거나 두 합이 홀수인경우
    if(sumQueue1 === sumQueue2) return count;
    if((sumQueue1 + sumQueue2) % 2 !== 0) return -1
    
    const target = (sumQueue1 + sumQueue2) / 2;
    
    let totalSum = getSum(concatQueue.slice(start, end)); 
    
    for(let i = 0; i <= ((queueLen-1)*3); i++){
        if(target < totalSum) {
            totalSum -= concatQueue[start];
            start++;
        } else if(target > totalSum) {
            totalSum += concatQueue[end];
            end++;
        } else if(target === totalSum) {
            return count;  
        } 
        count++;
    }
    return -1;
}

최근에 읽었던 책 덕분에 원인은 바로 알았지만 해결방법이 좀처럼 떠오르지않아 푸는데 오기가 생겼던 문제였다.(몇시간을..) 검색해보니 꽤 쉬운 방법으로 풀 수 있었고, 오랜만에 재밌는 알고리즘이었다. 코드스테이츠 수업들을때 알고리즘 문제에서도 비슷하게 포인터를 활용해 풀었던게 있었던거로 기억하는데 한번 찾아봐야겠다.