[프로그래머스] 두 큐 합 같게 만들기 (JS)

hhkim·2023년 10월 11일
0

Algorithm - JavaScript

목록 보기
156/188
post-thumbnail

풀이 과정

  1. 각 큐 요소들의 합 구하기
  2. 두 큐의 합이 같지 않은 동안 반복
  3. 합이 작은 곳에 합이 큰 곳의 첫 번째 요소를 옮기기: 결과 +1, 두 큐의 합 조정
    이때 shift()는 연산 비용이 크기 때문에 push()만 실행하고 큐 가장 앞의 위치를 인덱스에 저장
  4. 결과가 한 큐 길이 * 3보다 커졌으면 방법이 없는 것이므로 -1 리턴
    => 두 큐의 길이가 같으므로 최악의 경우를 가정

코드

function solution(queue1, queue2) {
  let result = 0;
  const maxResult = queue1.length * 3;
  let [sum1, sum2] = [
    queue1.reduce((a, c) => a + c, 0),
    queue2.reduce((a, c) => a + c, 0),
  ];
  let [i1, i2] = [0, 0];
  while (sum1 !== sum2) {
    if (result >= maxResult) return -1;
    if (!queue1[i1] || !queue2[i2]) return -1;
    if (sum1 < sum2) {
      queue1.push(queue2[i2++]);
      sum1 += queue1.at(-1);
      sum2 -= queue1.at(-1);
    } else {
      queue2.push(queue1[i1++]);
      sum1 -= queue2.at(-1);
      sum2 += queue2.at(-1);
    }
    ++result;
  }
  return result;
}

🦾

처음에 문제만 보고서 못 풀 것 같다는 생각이 들었는데 막상 시작하니까 금방 풀렸다.
shift() 때문에 시간 초과 나는 거랑, 최악의 경우를 두 큐 길이의 합으로 해서 1번 테스트 케이스가 통과 못하는 것 때문에 시간을 좀 썼다.
[1, 1, 1, 1, 1] [1, 1, 1, 9, 1] => 12 같이 두 큐의 합보다 결과가 커지는 경우가 있으므로, 최악의 경우를 큐 길이 * 3으로 넉넉히 잡아줬다.

0개의 댓글