[2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기- JS

문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

문제 설명
길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.
따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

제한사항
1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
1 ≤ queue1의 원소, queue2의 원소 ≤ 109
주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

문제 풀이 힌트 

이 문제는 2가지 방법으로 풀어낼 수 있다.

01. 투 포인터를 사용하는 방법 

02. 큐를 사용하는 방법 

 

투포인터로 푸는 방법부터 알아보자. ! 

 

01. 투 포인터를 사용하는 방법은 주어진 두 큐 배열을 하나의 배열로 취급하면서 시작된다. 

즉, 

let queue1 = [1,2,3]

let queue2 = [4,5,6]

위 큐가 주어졌을 때, 

const queue = [1,2,3,4,5,6] 으로 생각한다는 것이다. 

 

queue1의 합은 현재 6이고, queue2의 합은 현재 15이다. 

우리의 target은 12가 되어야 한다. 

queue1의 합을 기준으로 queue1이 12가 되도록 만들어 보자. 

 

이때,  startIdx는 0, endIdx는 3으로 설정한다. 

현재 queue1의 합은 6으로 target 점수인 12보다 작다. 

그럼, endIdx의 값을 queue1 합에 추가해주고, endIdx 를 1을 올려준다. 

 

만약, queue1의 합이 target 점수보다 클땐 ? 

startIdx의 값을 queue1의 값에서 빼주고 startIdx를 1올려준다. 

 

idx를 하나 옮길 때마다 count++ 한다. 

언제까지 반복해야할까? 

이 포인터들이 한바퀴를 돌아 제자리일 때 그때이다 ! 

따라서 count 값이 내가 정한 limit 값 전까지만 반복문을 돌려준다. 

 

정답 풀이 코드 (투포인터 이용한 코드)

function solution(queue1, queue2) {
   let sumQ1 = sum(queue1);
   let sumQ2 = sum(queue2);
   let target = (sumQ1 + sumQ2)/2; 
   let startIdx = 0; 
   let endIdx = queue1.length
   let count = 0; 
   const queue = [...queue1, ...queue2]
   let limit = queue1.length *4
   while(count <= limit){
       if(sumQ1 === target){
           return count
       }
       if(sumQ1 > target){
           sumQ1 -= queue[startIdx++];  
       }else{
           sumQ1+=queue[endIdx++]; ; 
       }
       count++; 
   }
    return -1
}
const sum = (arr) => arr.reduce((acc, cur) => acc+ cur,0)

 

 

02. 큐를 사용하는 방법

 

오답 풀이 코드

배열을 큐 형식으로 사용한 방법으로는 시간 초과가 난다. 

왜 ? 배열의 shift() 때문이다. 배열 맨 앞 요소를 빼면 뒤에 요소들을 한칸씩 앞으로 땡겨야 한다.  

function solution(queue1, queue2) {
    let cnt = 0;  
    let deadLine = queue1.length + queue2.length
    while(true){
        let oneSum = queue1.reduce((a,b) => a+b,0);
        let twoSum = queue2.reduce((a,b) => a+b,0);
        if(oneSum === twoSum){
            return cnt; 
            break; 
        }else if(oneSum < twoSum){
           queue1.push(queue2.shift()); 
        }else{
            queue2.push(queue1.shift()); 
        }
        cnt++;
        if(cnt > deadLine){
            return -1
            break; 
        }
    }
}