프로그래머스 두 큐 합 같게 만들기 JavaScript
2023년 2월 7일
문제 풀이
투포인터를 이용해서 푼 문제.
매개변수 queue1, queue2의 합을 구해 목푯값을 구하고, MAXCIRCUIT을 정의한다.
MAXCIRCUIT: 포인터가 움직일 수 있는 최대 횟수. 두 개의 큐를 합쳐 조회할 것인데 최악의 경우 q1Pointer가 0부터 끝에서 한 칸 전까지 이동 queue1.length * 2 - 2 + q2Pointer가 queue1.length 부터 끝까지 이동 queue1.length - 1 => queue1.length * 3 - 3이다.
예: [20, 20, 20, 20], [1, 1, 83, 1] 일 때,
index.md
0: [20, 20, 20, 20] [1, 1, 83, 1]
1: [20, 20, 20, 20, 1] [1, 83, 1]
2: [20, 20, 20, 20, 1, 1] [83, 1]
3: [20, 20, 20, 20, 1, 1, 83] [1]
4: [20, 20, 20, 1, 1, 83] [1, 20]
5: [20, 20, 1, 1, 83] [1, 20, 20]
6: [20, 1, 1, 83] [1, 20, 20, 20]
7: [1, 1, 83] [1, 20, 20, 20, 20]
8: [1, 83] [1, 20, 20, 20, 20, 1]
9: [83] [1, 20, 20, 20, 20, 1, 1]
=> 9번 4 * 3 - 3 = 9
MAXCIRCUIT까지 for 문을 돌 때,
q1Sum이 목푯값과 같으면 리턴q1Sum이 목푯값보다 큰 경우q1Sum -= queue[q1Pointer++]
(queue1 pop queue2 push)q1Sum이 목푯값보다 작은 경우q1Sum += queue[q2Pointer++]
(queue2 pop queue1 push)
MAXCIRCUIT까지 for 문을 돈 후 목푯값을 못 찾았으면 합을 같게 만들 수 없는 경우로 -1을 리턴한다.
solution.js
function solution(queue1, queue2) {
let q1Sum = queue1.reduce((a, b) => a + b, 0);
const q2Sum = queue2.reduce((a, b) => a + b, 0);
const target = (q1Sum + q2Sum) / 2;
const MAXCIRCUIT = queue1.length * 3 - 3;
const queue = [...queue1, ...queue2];
let q1Pointer = 0;
let q2Pointer = queue1.length;
for (let i = 0; i <= MAXCIRCUIT; i++) {
if (q1Sum === target) {
return i;
}
q1Sum > target ? q1Sum -= queue[q1Pointer++] : q1Sum += queue[q2Pointer++];
}
return -1;
}