[알고리즘/프로그래머스/카카오] 두 큐 합 같게 만들기(JS, 투포인터)

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=javascript 

프로그래머스

 

풀이

---

길이가 같은 두 개의 큐에서 배열의 첫 번째 원소를 다른 배열에 마지막에 넣는 과정을 반복했을 때 두 큐의 합이 같아지기 위한 최소 작업 횟수를 구하는 문제이다. 처음에는 이해가 어려워서 해당 블로그의 그림을 참고하였다.

 

queue1과 queue2를 합친 하나의 배열 queue를 만든다.

p1을 queue1의 시작점(0)으로, p2를 queue2의 시작점(queue1.length)으로 초기화한다. 

target은 queue1과 queue2의 합의 절반인 값으로, sum1이 이 값과 같아지면 작업 횟수인 count를 반환한다.

이때 전체 배열의 길이가 queue1.length*2이므로 두 포인터의 가능한 최대 이동 횟수는 그 두 배인 queue1.length * 4이다.

 

따라서 최대 이동 가능한 횟수까지 반복하면서 sum1이 target과 같은지 비교하고, 아래와 같이 값에 따라 포인터를 이동시킨다.

• (sum1이 target과 같으면) 두 큐의 합이 같아진 시점이므로 count를 반환한다.
• (sum1이 target보다 작으면) queue1에 더 더해줘야 하므로 p2의 값을 더해주고 p2를 오른쪽으로 이동한다.
• (sum1이 target보다 크면) queue1에서 값을 빼줘야하므로 p1의 값을 빼주고 p1을 오른쪽으로 이동한다.

function sum(arr) {
    return arr.reduce((acc, cur) => acc + cur, 0)
}

function solution(queue1, queue2) {
    let sum1 = sum(queue1)
    let sum2 = sum(queue2)
    let p1 = 0 // queue1의 시작점
    let p2 = queue1.length // queue2의 시작점 
    
    const target = (sum1 + sum2) / 2
    const queue = [...queue1, ...queue2]
    const end = queue1.length * 4 // 포인터의 최대 이동 거리
    
    for (let count = 0;count < end;count++) {
        if (sum1 === target) {
            return count
        }
        
        // queue1의 합이 작은 경우: p2를 오른쪽으로 한 칸 이동 
        if (sum1 < target) {
            sum1 += queue[p2]
            p2 += 1
        } else {
            // queue1의 합이 큰 경우: p1을 오른쪽으로 한 칸 이동
            sum1 -= queue[p1]
            p1 += 1
        }
    }
    
    return -1;
}

 

 

 

REF

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

https://koguri.tistory.com/108