프로그래머스) 두 큐 합 같게 만들기(투포인터) JS

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

프로그래머스

문제 해결 방법

이 문제를 js로 해결하기 위해서는 투포인터로 풀어야한다. 카카오에서 c++로 풀이를 제공했는데, 이 방식대로 문제를 풀면 js에서는 시간 초과가 떴다.

코드

function add(ary) {
  return ary.reduce((a, b) => a + b, 0);
}

function solution(queue1, queue2) {
  var answer = 0;
  let total = [...queue1, ...queue2];
  let start = 0;
  let end = queue1.length;

  let firstAry = add(total.slice(start, end));
  let goal = add(total) / 2;

  while (answer < total.length * 2 && firstAry !== goal) {
    if (firstAry < goal) {
      firstAry += total[end];
      end++;
    } else if (firstAry > goal) {
      firstAry -= total[start];
      start++;
    }
    answer++;
  }

  if (firstAry !== goal) answer = -1;

  return answer;
}

예시)

사진처럼 2개의 큐가 주어졌을 때를 예시로 문제 설명을 해보겠다.

 

1. queue1과 queue2를 합쳐준다.

위 사진처럼 total 배열에 queue1, queue2를 합쳐준다.

 

2. start, end, firstAry, goal 변수 값 할당

start는 0부터 시작하고 end는 queue1의 길이로 둔다.

firstAry에 queue1의 값들 합을 넣어준다.

goal에는 total의 전체 값의 합/2를 하여 넣어준다.

 

3. while문에서 start, end를 기반으로 비교

-queue1 < queue2인 경우

firstAry가 queue1의 합이므로 14이다. goal의 값은 15라서 queue2의 값이 queue1보다 크다.

따라서 queue2에서 값을 빼서 queue1에 넣어줘야한다. 그러므로 firstAry에 total[end]를 더해주고 end++를 한다.

while문이 돌아가는 한 answer는 계속 1씩 증가한다.

 

-queue1 > queue2인 경우

여기에서는 queue1값이 더 크기 때문에 queue1에서 값을 빼서 queue2에 넣어줘야한다. 

따라서 firstAry에서 total[start]를 빼주고 start++를 한다.

마찬가지로 while문이 돌아가는 한 answer는 계속 1씩 증가한다.

 

-queue1 === queue2인 경우 

두 배열의 합이 같아지면 while에 조건을 걸어 반복문이 멈추도록 한다.

 

4. while문이 끝나고 firstAry !== goal인 경우

answer를 -1로 바꿔준다.