[javascript] 두 큐 합 같게 만들기

이제 익숙해져버린 시간초과... 이러면 안대!!!
12월 목표 : 시간초과와 멀어지자

<문제 요약>

• 길이가 같은 두개의 큐.
• 하나의 큐를 골라 원소 추출.
• 추출된 원소를 다른 큐에 집어넣음.
• 각 큐의 원소의 합이 같도록 만듦.
• return : 이때 필요한 작업의 최소 횟수는?
• pop과 insert를 합쳐서 1회로 간주.
  • pop을 하면 배열의 첫번째 원소가 추출.
  • insert를 하면 배열의 끝에 원소가 추가.

1. 시간초과 코드 (66점)

function solution(queue1, queue2) {
    var answer = 0;
    var sum1 = queue1.reduce((sum, cur) => {return sum + cur});
    var sum2 = queue2.reduce((sum, cur) => {return sum + cur});
    var len = queue1.length * 2;
    
    for (let i = 0; i < len; i++)
    {
        if (queue1.length > 0)
            sum1 = queue1.reduce((sum, cur) => {return sum + cur});
        else
            sum1 = 0;
        if (queue2.length > 0)
            sum2 = queue2.reduce((sum, cur) => {return sum + cur});
        else
            sum2 = 0;
        if (sum1 == sum2)
            break;
        if (sum1 < sum2)
            queue1.push(queue2.shift());
        else
            queue2.push(queue1.shift());
        answer++;
    }
    if (answer == len)
        answer = -1;
    
    return answer;
}

2. 시간초과 제외 실패였던 부분 잡아내기 (70점)

 var len = queue1.length * 2; # 에서
 var len = queue1.length * 3; #으로 바꿨더니 점수가 오른다??
 # *4는 바꿔봤자 시간초과만 더 커짐

• 테스트 1을 제외하고 틀린 부분은 전부 시간초과였는데, 단순 실패였던 test1이 통과로!!
  • 움직이는 횟수가 queue1.length + queue2.length 정도면 충분할 줄 알았는데, 그게 아니었다는 것을 깨달음.
  • 시간초과를 해결하다가 이유를 깨달음 : queue1은 처음부터 끝까지 2번, queue2는 처음부터 끝까지 1번(그 반대의 경우도 상관없음. 기준을 어디에 두냐의 차이) 하게되어야 전부 탐색된다는 사실을 알게됨. 말로 설명하기는 어려운데, 문제를 풀다보면 모두 그 이유를 깨달을 듯!!!

3. 시간초과 해결방안 탐색

• 시간초과 이유에 대해 생각해보자
  • 계속 반복되는 reduce. 굳이 그럴필요가 있을까?
  • push, shift는 시간을 얼마나 잡아먹을까?
    
    
    

4. 시간초과 해결하기 (86점->100점)

• 계속 반복되는 reduce를 없애기. (시간초과의 가장 큰 비율을 차지했을 것이라는 생각)

  function solution(queue1, queue2) {
    var answer = 0;
    var sum1 = queue1.reduce((sum, cur) => {return sum + cur});
    var sum2 = queue2.reduce((sum, cur) => {return sum + cur});
    var len = queue1.length * 3;
    for (let i = 0; i < len; i++)
    {
        if (sum1 == sum2)
            break;
        if (sum1 < sum2)
        {
            var tmp = queue2.shift();
            queue1.push(tmp);
            sum1 += tmp; sum2 -= tmp;
        }
        else
        {
            var tmp = queue1.shift();
            queue2.push(tmp);
            sum1 -= tmp; sum2 += tmp;
        }
        answer++;
    }
    if (answer == len)
        answer = -1;
    return answer;
  }

  
  - 역시나!!! 시간이 확 단축되었음.

  
  - 4개 시간초과로 86.7점을 얻음!

• push, shift는 시간을 얼마나 잡아먹을까?

  shift 시간 복잡도 : O(n) 
   push 시간 복잡도 : O(1) # 맨 마지막에 요소를 집어넣기 때문에 시간이 크게 소요되지 않음

• shift를 없애야 함을 깨닫게 됨!
  - 하지만 지금 코드에서 어떻게 shift 없이 작동시키지??

  function solution(queue1, queue2) {
   var answer = 0;
   var sum1 = queue1.reduce((sum, cur) => {return sum + cur});
   var sum2 = queue2.reduce((sum, cur) => {return sum + cur});
   var len = queue1.length;
   var data;
   var q1_pos = [[0 ,len - 1], [0, -1]];
   for (let i = 0; i < len * 3; i++)
   {
       if (sum1 == sum2)
           return answer;
       if (sum1 < sum2)
       {
           if (q1_pos[1][1] == len)
           {
               data = q1_pos[0][1] + q1_pos[0][0] + 2;
               if (data > len - 1) data = data - len;
               q1_pos[0][1]++;
               data = queue1[data];
           }
           else
           {
               q1_pos[1][1]++;
               data = queue2[q1_pos[1][1]];
           }
           sum1 += data;
           sum2 -= data;
       }
       else
       {
           if (q1_pos[0][1] == -1)
           {
               q1_pos[1][1]--;
               data = queue2[q1_pos[1][1]];
           }
           else
           {
               data = queue1[q1_pos[0][0]];
               q1_pos[0][1]--;
               if (q1_pos[0][0] == len - 1)
                   q1_pos[0][0] = 0;
               else
                   q1_pos[0][0]++;
           }
           sum1 -= data;
           sum2 += data;
       }
       answer++;
   }
   return -1;
  }

  
  - q1_pos배열을 통해 [[queue1에서의 시작점, 길이],[queue2에서의 시작점, 길이]]를 주고, queue1 입장이 되어 값을 움직이며 해결해 나간 결과, 해결!

• 하나 아쉬운 점은, 코드가 너무 길다!! 이게 최선일까?

5. 코드 줄이기

• queue1과 queue2를 따로 생각하지 말고, 합쳐서 하면 자연스럽게 해결된다는 것을 알게 됨!
• queue1은 0 ~ (queue1.length+queue2.length)까지 갈 수 있고, queue2는 (queue1.length + 1) ~ (queue1.length+queue2.length)까지 갈 수 있다 생각하면 됨.
  • len * 3인 이유를 더 명확히 표현할 수 있음.

function solution(queue1, queue2) {
    var answer = 0;
    var q = [...queue1, ...queue2];
    var len = queue1.length;
    var q1 = 0;
    var q2 = len;
    var sum = queue1.reduce((sum, cur) => {return sum + cur});
    var goal = q.reduce((sum, cur) => {return sum + cur}) / 2;
    
    for(let i = 0; i < len * 3; i++)
    {
        if(sum == goal){
            return answer;
        }
        if(sum < goal){
            sum += q[q2];
            q2++;
        }else if(sum > goal){
            sum -= q[q1];
            q1++;
        }
        answer++;
    } 
    return -1;
}

• 거의 절반으로 줄었다!! yeah~~🧡