풀이 과정
두 개의 큐를 하나의 큐로 이어붙여서 계산하는 것까진 알겠지만,이 후 어떤 큐를 앞에 두고 계산을 해야 최소 작업 횟수를 구할 수 있을지 고민하다가 도저히 생각나지 않아 다른 풀이들을 찾아보았습니다.
투 포인터
1차원 배열에서 각자 다른 원소를 가리키는 두 개의 포인터를 조작하여 원하는 값을 얻는 형태입니다.
따라서, 투 포인트 알고리즘이라고 부릅니다.
배열에서 두 개의 포인터를 이용하여 순차적으로 접근하여 두 포인터 구간의 값이 타겟값과 같을 때까지 포인터를 조작하여 원하는 값을 얻을 수 있습니다.
이중 반복문을 이용하여 값을 얻을 수 있지만, 시간 복잡도가 O(n²)이기 때문에 데이터가 많다면 시간초과가 발생할 수 있습니다.
이때 투 포인터를 사용한다면 배열을 한 번만 탐색하기 때문에, 시간 복잡도가 O(n)으로 시간초과 문제를 해결할 수 있습니다.
예시 문제
숫자로 이루어진 배열
array와 타겟값target이 주어질 때,array에서 두 원소의 합이target이 되는 순서쌍을 모두 구하세요.
이중 반복문
const array = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28];
const target = 27;
const result = [];
for (let i = 0; i < array.length; i++) {
for (let j = i + 1; j < array.length; j++) {
const sum = array[i] + array[j];
if (sum === target) result.push((array[i], array[j]));
}
}
console.log(result); // [ [ 5, 22 ], [ 11, 16 ] ]투 포인터
- 포인터
left는 배열의 시작점, 포인터right는 배열의 끝점을 가리킵니다. left와right가 만날 때까지 다음 과정을 반복합니다.- 각 포인터
left와right가 가리키는 값의 합인sum이target과 같다면,result에 포인터left와right가 가리키는 값을 추가하고,left는 1 증가,right는 1 감소 시킵니다. sum이target과 작다면,left를 1 증가 시킵니다.sum이target과 같다면,right를 1 감소 시킵니다.
- 각 포인터
const array = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28];
const target = 27;
const result = [];
let left = 0;
let right = array.length - 1;
while (left < right) {
const sum = array[left] + array[right];
if (sum > target) {
right -= 1;
}
else if (sum < target) {
left += 1;
}
else {
result.push([array[left], array[right]]);
left += 1;
right -= 1;
}
}
console.log(result); // [ [ 5, 22 ], [ 11, 16 ] ]성능 비교
링크를 통해 직접 확인할 수 있습니다:)
나의 풀이
for loop
const getSum = (arr) => {
return arr.reduce((acc, cur) => acc + cur, 0);
}
function solution(queue1, queue2) {
// 두 개의 큐를 하나의 큐로 붙이기
const totalQueue = [...queue1, ...queue2];
const sumOfTotalQueue = getSum(totalQueue);
// 두 큐에 담긴 모든 원소의 합이 홀수 인 경우, -1 반환
if(sumOfTotalQueue % 2 !== 0) return -1;
// 각 큐의 원소 합
const sumOfEachQueue = sumOfTotalQueue / 2;
// 최대 작업 수
const maxCount = queue1.length * 3;
let sum = getSum(queue1);
let startIndex = 0;
let endIndex = queue1.length;
for (let count = 0; count < maxCount; count++) {
// 각 큐의 원소 합이 같아지는 경우 count를 반환
if (sum === sumOfEachQueue) return count;
// queue1 원소 합이 각 큐의 원소 합보다 작은 경우
if (sum < sumOfEachQueue) {
// totalQueue의 endIndex에 해당하는 원소 값을 더한다.
sum += totalQueue[endIndex];
// endIndex를 다음 인덱스로 이동 시킨다.
endIndex += 1;
}
// queue1 원소 합이 각 큐의 원소 합보다 큰 경우
else if (sum > sumOfEachQueue) {
// totalQueue의 startIndex에 해당하는 원소 값을 뺀다.
sum -= totalQueue[startIndex];
// startIndex를 다음 인덱스로 이동 시킨다.
startIndex += 1;
}
}
// 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 반환
return -1;
}while
const getSum = (arr) => {
return arr.reduce((acc, cur) => acc + cur, 0);
}
function solution(queue1, queue2) {
const totalQueue = [...queue1, ...queue2];
const sumOfTotalQueue = getSum(totalQueue);
if(sumOfTotalQueue % 2 !== 0) return -1;
const sumOfEachQueue = sumOfTotalQueue / 2;
const maxCount = queue1.length * 3;
let count = 0;
let intervalSum = getSum(queue1);
let startIndex = 0;
let endIndex = queue1.length;
while (count < maxCount) {
if (intervalSum === sumOfEachQueue) return count;
if (intervalSum < sumOfEachQueue) {
intervalSum += totalQueue[endIndex];
endIndex += 1;
} else if (intervalSum > sumOfEachQueue) {
intervalSum -= totalQueue[startIndex];
startIndex += 1;
}
count += 1;
}
return -1;
}참고
