[투 포인터] 두 큐 합 같게 만들기

[ericagong]

⭐ 성찰

1. 특정 조건을 만족하는 특정 범위를 구해야하는 경우 -> 투포인터 떠올리기
2. O(n)을 만족해야하는 경우 -> 투포인터 떠올리기
3. fast fail이 가능한 경우 -> 효율성을 위해 사전에 실패 조건 작성해주기 단! 정확한 경우만 수행!!

⭐ 투 포인터 풀이 방향

1. 특정 범위가 만족해야할 조건 정의하기
2. while문의 종료 조건 파악하기: eg. 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000 조건에 의해 300000으로 잡아서 for문을 돌려줄 수 있음 -> 종료 조건 파악이 어렵다면, 우선 시도해보기 : 길이 * 2, 3, ....

❓ 문제 상황

두 큐 합 같게 만들기

👨‍💻 문제 해결

✅ 1차 풀이: queue를 통해 구현(시간 초과)

function solution(queue1, queue2) {
  let q1_sum = queue1.reduce((acc, cur) => acc + cur, 0);
  let q2_sum = queue2.reduce((acc, cur) => acc + cur, 0);
  let total_sum = q1_sum + q2_sum;

  if (total_sum % 2 !== 0) return -1;

  let cnt = 0;
  while (queue1.length !== 0 && queue2.length !== 0) {
    if (q1_sum === q2_sum) return cnt;
    else if (q1_sum >= q2_sum) {
      const elem = queue1.shift();
      queue2.push(elem);
      q1_sum -= elem;
      q2_sum += elem;
    } else {
      const elem = queue2.shift();
      queue1.push(elem);
      q2_sum -= elem;
      q1_sum += elem;
    }
    cnt += 1;
  }
  return -1;
}

✅ 2차 풀이: 투포인터

1. 범위 내 달성 조건 구하기: target = sum
2. while 문 제약 조건 파악하기: 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000 조건에 의해 300000으로 잡아서 for문을 돌려줄 수 있음
   • 종료 조건 파악이 어렵다면, 우선 시도해보기 : 길이 * 2, 3, ....

     function solution(queue1, queue2) {
     const TOTAL_ARRAY = [...queue1, ...queue2];
     const MAXCOUNT = 4 * TOTAL_ARRAY.length;
     const sum = (array) => array.reduce((a, b) => a + b);
     const TARGET = sum(TOTAL_ARRAY) / 2;
     let count = 0;
     let start = 0;
     let end = queue1.length;
     let totalSum = sum(TOTAL_ARRAY.slice(start, end));
     while (count <= MAXCOUNT) {
     if (TARGET > totalSum) {
     totalSum += TOTAL_ARRAY[end];
     end++;
     } else if (TARGET < totalSum) {
     totalSum -= TOTAL_ARRAY[start];
     start++;
     } else if (TARGET === totalSum) {
     return count;
     }
     count++;
     }
     return -1;
     }