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

⭐⭐ 문제

코딩테스트 연습 > 2022 KAKAO TECH INTERNSHIP > 두 큐 합 같게 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/118667

📌 문제 설명

• 매개변수 : 길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2
• return : 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수
  (단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return)
• 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행
• queue1 = [3, 2, 7, 2]
  queue2 = [4, 6, 5, 1] 두 배열의 합이 30이므로 각 큐의합을 15로 만들어야함
• queue1의 3을 pop하여 queue2에 넣으면 [2,7,2] , [4,6,5,1,3] 이를 1회 수행이라고함

📌 문제 풀이

1. 두 배열의 합 / 2의 값 구하기 -> sum
2. queue1Sum의 합이 sum 보다 큰지 or queue2Sum의 합이 sum 보다 큰지
3. 둘 중 큰쪽 값을 pop해서 다른쪽에 넣어주고 count ++;
4. queue1Sum === sum or queue2Sum === sum return.

시간초과..

try1.

function solution(queue1, queue2) {
  var answer = 0;

  const queue1Sum = [...queue1].reduce((a, b) => a + b);
  const queue2Sum = [...queue2].reduce((a, b) => a + b);
  if (queue1Sum === queue2Sum) return 0;

  const sum = [...queue1, ...queue2].reduce((a, b) => a + b) / 2;
  while (queue1.length > 0 && queue2.length > 0) {
    const queue1Sum = [...queue1].reduce((a, b) => a + b);
    const queue2Sum = [...queue2].reduce((a, b) => a + b);

    if (queue1Sum > sum) {
      const shift = queue1.shift();
      queue2.push(shift);
      answer++;
    }

    if (queue2Sum > sum) {
      const shift = queue2.shift();
      queue1.push(shift);
      answer++;
    }

    if (queue1.length === 0 || queue2.length === 0) return -1;
    if (queue1Sum === sum && queue2Sum === sum) {
      return answer;
    }
  }
  return answer === 0 ? -1 : answer;
}

왜 시간초과일까?!

1. shift, push 사용시 시간초과 발생.
2. shift의 경우, O(n)의 시간복잡도
3. shift 없이 하는 방법은 뭘까..?
4. index를 사용해서 해보자!

solved.

function solution(queue1, queue2) {
  var answer = 0;
  let triedCnt = 0,
    queue1Index = 0,
    queue2Index = 0,
    triedLength = (queue1.length + queue2.length) * 2;
  let sameQueue = false;
  let queue1Sum = queue1.reduce((acc, val) => acc + val, 0);
  let queue2Sum = queue2.reduce((acc, val) => acc + val, 0);

  while (triedCnt < triedLength) {
    if (queue1Sum > queue2Sum) {
      const element = queue1[queue1Index++];
      queue2Sum += element;
      queue1Sum -= element;
      queue2.push(element);
    } else if (queue1Sum < queue2Sum) {
      const element = queue2[queue2Index++];
      queue1Sum += element;
      queue2Sum -= element;
      queue1.push(element);
    } else {
      sameQueue = true;
      break;
    }

    triedCnt++;
  }

  return sameQueue ? triedCnt : -1;
}

triedLength = (queue1.length + queue2.length) 2;
여기서 2를 안해줘서 해맸었다...

solution([3, 3, 3, 3], [3, 3, 21, 3]); 케이스때문에..