Partition Array According to Given Pivot
MediumArrayTwo PointersSimulation
문제 설명
정수 배열 nums와 정수 pivot이 주어진다.
배열을 다음 조건에 맞게 재배치하여 반환해야한다.
pivot보다 작은 수는 앞쪽에 위치해야 한다.pivot보다 같은 수는 중간에 위치해야 한다.pivot보다 큰 수는 뒤쪽에 위치해야한다.nums에서의 상대적인 순서를 유지해야한다.
문제 풀이
Three-Array Partitioning
less,equal,grater세개의 배열을 사용한다.less:pivot보다 작은 수equal:pivot같은 수greater:pivot보다 큰 수
- 3개의 배열을 순서대로 합쳐서 반환한다.
function pivotArray(nums: number[], pivot: number): number[] {
const less: number[] = [];
const equal: number[] = [];
const greater: number[] = [];
for (const num of nums) {
if (num < pivot) {
less.push(num);
} else if (num > pivot) {
greater.push(num);
} else {
equal.push(num);
}
}
return [...less, ...equal, ...greater];
}복잡도
- 시간 복잡도:
- 공간 복잡도:
Two Pointers
pivot보다 작은 값과 큰 값을 동시에 배치하는 방식으로 해결할 수 있다.lessIndex:pivot보다 작은 값을 넣을 인덱스 (초기값:0)greaterIndex:pivot보다 큰 값을 넣을 인덱스 (초기값:nums.length - 1)
- 배열을 순회하면서, 두 개의 포인터(
lessIndex,greaterIndex)를 활용하여 한 번의 탐색으로 값을 배치한다.nums의 앞에서부터 탐색하며,pivot보다 작은 값을lessIndex에 저장하고lessIndex를 증가시킨다.nums의 뒤에서부터 탐색하며,pivot보다 큰 값을greaterIndex에 저장하고greaterIndex를 감소시킨다.- 이를 통해,
nums의 상대적인 순서를 유지할 수 있다.
- 배열을 순회한 후,
lessIndex와greaterIndex사이에pivot값들을 채워넣는다.
function pivotArray(nums: number[], pivot: number): number[] {
const n = nums.length;
const answer = new Array<number>(n).fill(0);
let lessIndex = 0;
let greaterIndex = n - 1;
for (let i = 0; i < n; i++) {
if (nums[i] < pivot) {
answer[lessIndex] = nums[i];
lessIndex += 1;
}
if (nums[n - i - 1] > pivot) {
answer[greaterIndex] = nums[n - i - 1];
greaterIndex -= 1;
}
}
while (lessIndex <= greaterIndex) {
answer[lessIndex] = pivot;
lessIndex += 1;
}
return answer;
}복잡도
- 시간 복잡도:
- 공간 복잡도: (결과 값에 대한 공간복잡도를 고려하지 않은 경우)