[알고리즘 연습] 프로그래머스 두 큐 합 같게 만들기 (LEVEL 2, 자바스크립트)

문제

프로그래머스

---

풀이

• 해당 문제를 자바스크립트로 풀 때 2개의 Queue를 사용해 shift/push로 구현하면 몇 개의 테스트 케이스에서 시간 초과가 발생하기 때문에 1개의 Queue를 사용한다.
• 고려해야 할 사항은 크게 2가지가 있었다.
  1. Queue의 상태에 따라 어떤 Queue에서 원소를 추출해서 어떤 Queue에 추가할 것인가
  2. 두 Queue의 합계가 같을 수 없는 경우 언제 반복문을 멈출 것인가
• 첫 번째 사항은 합계가 큰 Queue에서 원소를 추출하여 합계가 작은 Queue에 추가하는 방식으로 구현한다. (그리디)
• 두 번째 사항은 반복 횟수가 4 * n(n은 1개의 Queue 길이) 이상일 때 반복문을 멈춘다. 2 * n일 때 두 Queue는 서로 완전히 스왑되고 4 * n일 때 두 Queue는 처음 상태로 돌아온다.
• 추가적으로 포인터(a, b)가 가르키는 인덱스가 Queue의 길이를 초과할 수 있기 때문에 Queue의 원소에 접근할 때 Queue의 길이로 나눈 나머지를 사용한다.

소스 코드

function solution(queue1, queue2) {
    const n = queue1.length;
    const queue = [...queue1, ...queue2];
    let total1 = queue1.reduce((acc, cur) => acc + cur, 0);
    let total2 = queue2.reduce((acc, cur) => acc + cur, 0);
    let a = 0;
    let b = n;
    
    for (let i = 0; i < 4 * n; i++) {
      if (total1 === total2) return i;
      
      if (total1 > total2) {
        total1 -= queue[a % queue.length];
        total2 += queue[a % queue.length];
        a += 1;
      } else  {
        total1 += queue[b % queue.length];
        total2 -= queue[b % queue.length];
        b += 1;
      }
    }
    
    return -1;
}