89. 두 큐 합 같게 만들기 Javascript

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

프로그래머스

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 구하라
• 주어진 자료는 무엇인가?
   - queue1, queue2 : 길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2
• 조건은 무엇인가?
   - 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
   - 1 ≤ queue1의 원소, queue2의 원소 ≤ 109

2. 계획

• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
   - 시간 복잡도를 고려해야한다.

1. 두 큐를 더한 다음에 2로 나눈 값을 타겟으로 잡는다.
2. queue1과 queue2의 합계를 각각 구한다.
3. 반복은 큐 길이의 3배만큼 반복한다.
4. queue1Total > queue2Total 일때,
   queue2에 queue1이 가리키고 있는 pointer값을 push한다.
   queue1Total값에서 queue1이 가리키고 있는 pointer값을 빼고
   queue2Total값에서 queue1이 가리키고 있는 pointer값을 더한다.
   그리고 queue1이 가리키고 있는 pointer 위치를 +1 해준다.
5. queue1Total < queue2Total 일때,
   queue1에 queue2가 가리키고 있는 pointer값을 push한다.
   queue1Total값에서 queue1이 가리키고 있는 pointer값을 더하고
   queue2Total값에서 queue1이 가리키고 있는 pointer값을 뺀다.
   그리고 queue2가 가리키고 있는 pointer 위치를 +1 해준다.
6. queue1Total이 타켓과 같을때 반복문 종료와 i 값을 리턴한다.
7. 이 안에 해당하지 않으면 -1 리턴.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const solution = (queue1, queue2) => {
  const queueLength = queue1.length * 3;
  const Target = [...queue1, ...queue2].reduce((acc, cur) => acc + cur, 0) / 2;
  let queue1Total = queue1.reduce((acc, cur) => acc + cur, 0);
  let queue2Total = queue2.reduce((acc, cur) => acc + cur, 0);
  let queue1Pointer = 0;
  let queue2Pointer = 0;

  for (i = 0; i <= queueLength; i++) {
    if (queue1Total === Target) {
      return i;
    }

    if (queue1Total > queue2Total) {
      queue2.push(queue1[queue1Point]);
      queue1Total -= queue1[queue1Point];
      queue2Total += queue1[queue1Point];
      queue1Pointer += 1;
    } else if (queue1Total < queue2Total) {
      queue1.push(queue2[queue2Point]);
      queue1Total += queue2[queue2Point];
      queue2Total -= queue2[queue2Point];
      queue2Pointer += 1;
    }
  }

  return -1;
};

 

 

처음에는 push(), shift()를 사용했었는데 shift() 시간 복잡도가 O(N)이기 때문에 시간초과가 나온다. 
그래서 O(N)을 O(1)로 할 수 있는 방법을 생각해보다가 shift로 배열 맨 앞에 요소를 제거하는 것 말고 
인덱스를 사용해서 맨 처음 요소가 없다고 가정하고 문제를 풀었다.
ex) [2,3,4,5]가 있으면 2를 제거했다고 가정하기 위해서 배열 계산을 인덱스1번부터 하면 [3,4,5]이다.

그리고 처음 주어진 배열의 total 값을 한번 계산해두고
push()하면 total 값에 push()한것을 더하고 
배열의 인덱스가 이동하면 shift()했다고 가정한거니까 push한 값을 total 값에서 빼준다. 

이렇게 계속 반복하다가 total 값이 전체 배열의 요소를 더한 값의 반이 되면 멈추고 반복횟수를 리턴해주었다.