두 큐 합 같게 만들기 JavaScript

💡두 큐 합 같게 만들기

✔️ 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=javascript

방법1. 두 배열의 길이를 똑같이 하는 방법
방법2. 두 배열의 길이가 다른 배열 두개를 만드는 법

이렇게 구분지어서 문제를 해결하려고 했다.


방법1.

    let trynum = 0;
    for(let i = 0; i<queue1.length; i++){
        trynum++;
        let idx1 = arr1.pop();
        let idx2 = arr2.pop();
        arr1.push(idx2);
        arr2.push(idx1);
        let sum = arr1.reduce((prev, cur)=> prev+ cur,0);
        if(sum === total){
            answer = trynum*2;
            break;
        }
    }
    answer = answer === -2? 300000 : answer;

방법2.

    arr1 =  [...queue1];
    arr2 = [...queue2];
    arr2.reverse();
    let index = -1, num = 0;
    for(let i = 0; i<arr2.length; i++){
        let sum = 0;
        sum+= arr2[i];
        if(sum === total){
            console.log('1');
            index = i;
            num = 1;
            break;
        }
        if(sum > total) break;
        for(let j = i+1; j<arr2.length; j++){
            sum+= arr2[j];
            if(sum > total) break;
            if(sum === total){
                index = i;
                num = j-i+1;
                break;
            }
        }   
    }
    
    if(index === -1){
        return -1;
    }
    console.log(arr1.length, arr2.length, index, num)
    let idxanswer = arr1.length + 2*arr2.length - 2*index - num;
    answer = Math.min(answer, idxanswer);

근데 어쩐지..안풀린다..
일단 배열을 가지고 메서드를 사용하니 시간도 오래걸렸다.

풀이법

해결을 위해 다중포인터를 사용하면 각각 다른 원소를 가리키며 원하는 값을 얻고, 또한 배열에서 실제 값을 뺐다 넣었다 하는게 아니라 시간도 줄일 수 있다.

queue1과 queue2를 합친 하나의 queue를 만든다

최대 queue1길이 * 3만큼 반복하면서 sum1이 target보다 크면 queue2의 포인터를 증가시키고, 작다면 queue1의 포인터를 증가시킨다

• 최대 반복횟수의 경우 처음에는 queue길이*2배 만큼 해주면 될거라고 생각했으나 testcase1이 틀렸다
• 예를들어 [11111] [11191] 이라는 두 queue가 있을경우

1. [11111 11191][ ] : 5회
2. [91][11111111] : 8회
3. [9][111111111] : 1회
   이렇게 queue1길이*3배를 넘을 수 없다

코드

function solution(queue1, queue2) {
    const getSum = (arr)=>
        arr.reduce((prev, cur)=> prev+cur, 0);
    let sum1 = getSum(queue1);
    let sum2 = getSum(queue2);
    
    let pointer1 = 0, pointer2 = queue1.length;
    const target = (sum1+ sum2)/2;
    const queue = [...queue1, ...queue2];
    const end = queue1.length*3;
    
    for(let i = 0; i<end; i++){
        if(sum1 === target){
            return i;
        }
        if(sum1 > target){
            sum1 -= queue[pointer1++];
        }else{
                        console.log('2');
            sum1 += queue[pointer2++];
        }
    }
    return -1;
}