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

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

프로그래머스

 

🤔 해결방법

1. 두 큐를 하나의 배열로 합치고 원소의 합과 목표값을 구하기

2. 두 포인터를 설정하고 두 포인터 사이 원소들의 합이 목표값보다 크면 start + 1, 작으면 end + 1

3. 합친 배열의 길이 x 2 번의 작업 후에도 목표값과 일치하지 않으면 -1 반환

 

 

🔑 풀이

적절한 풀이 방법이 떠오르지 않아 카카오 기술 블로그에 올라온 해설을 참고했고 투 포인터를 사용해 푸는 문제였다.

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

2022 테크 여름인턴십 코딩테스트 해설

 

먼저 두 큐를 합치고 총합과 목표값을 구한다.

두 포인터는 각각 합친 배열의 인덱스를 의미하므로 start는 0, end는 끝 값인 큐의 길이로 놓는다.

 

문제의 조건에 따라 두 큐의 합을 동일하게 만들려면 원소를 하나의 큐에서 다른 큐로 이동시켜야 한다.

이는 배열의 경계(포인터)를 하나씩 움직이는 것과 같다.

예를 들어, 큐가 [1, 2, 3]과 [4, 5, 6]이라면, 이 둘을 합친 배열은 [1, 2, 3, 4, 5, 6]이 된다.

만약 첫 번째 큐에서 1을 제거하고 두 번째 큐에 추가한다면, 첫 번째 큐는 [2, 3]이 되고 두 번째 큐는 [4, 5, 6, 1]이다.

이는 합친 배열에서 포인터를 하나 오른쪽으로 움직인 것과 같다.

 

각 큐의 크기가 n이라면 합친 배열의 크기는 2n이고, 포인터는 합친 배열의 맨 왼쪽에서부터 맨 오른쪽까지 움직일 수 있으므로 한 포인터는 최대 2n번 움직일 수 있다.

따라서 두 개의 포인터 (start와 end)를 사용한다면 총 움직임의 수는 최대 4n, 즉 합친 배열의 크기의 2배라고 볼 수 있다.

 

두 포인터 사이에 있는 모든 요소의 합이 목표값보다 크면 숫자를 빼줘야 하므로 start에 있는 요소를 빼주고 start는 오른쪽으로 한 칸 밀어준다.

두 포인터 사이에 있는 모든 요소의 합이 목표값보다 작으면 숫자를 더해줘야 하므로 end에 있는 요소를 더해주고 end는 오른쪽으로 한 칸 밀어준다.

 

4n번의 작업 후에도 두 큐의 합을 동일하게 만들지 못한 경우, 그 이후로는 더 이상 새로운 가능성이 없으므로 -1을 반환한다.

 

최종 코드는 다음과 같다.

function solution(queue1, queue2) {
      const totalArray = [...queue1, ...queue2]; // 두 큐 합치기
      const totalSum = totalArray.reduce((acc, val) => acc + val); // 두 큐의 총합
      const targetSum = totalSum / 2; // 목표값

      // 두 포인터
      let start = 0;
      let end = queue1.length;
      let currentSum = queue1.reduce((acc, val) => acc + val); // 현재 queue1의 합

      let count = 0;
      const max = 2 * totalArray.length;  // 최대로 움직일 수 있는 횟수

      while (count < max) {
          if (currentSum === targetSum) {
              return count;
          //  두 포인터 내에 있는 모든 원소의 합이 목표값보다 클 때
          } else if (currentSum > targetSum) {
              currentSum -= totalArray[start];
              start++;
          //  두 포인터 내에 있는 모든 원소의 합이 목표값보다 작을 때
          } else {
              currentSum += totalArray[end];
              end++;
          }
          count++;
      }

      return -1;  // 불가능한 경우
  }

 

투포인터 문제는 아직 익숙하지 않은 것 같다😥