[코테연습] 2161. Partition Array According to Given Pivot

https://leetcode.com/problems/partition-array-according-to-given-pivot/description/?envType=daily-question&envId=2025-03-03

 

1. 문제 타입

• 배열(Array)
• 정렬(Sorting)
• 투 포인터(Two Pointers)
• 단순 구현(Simulation/Implementation)

---

2. 문제 분석

📌 문제 설명

• 정수 배열 nums 와 정수 pivot이 주어진다.
• 배열을 다음 규칙에 따라 재배열해야 한다:
  1. pivot보다 작은 원소들을 먼저 배치한다.
  2. pivot과 같은 원소들을 중간에 배치한다.
  3. pivot보다 큰 원소들을 마지막에 배치한다.
  4. 기존 nums 배열에서 상대적인 순서는 유지해야 한다. (Stable Sort)

 

 

3. 문제 풀이

💡 해결 방법

배열을 pivot보다 작은 값, pivot과 같은 값, pivot보다 큰 값으로 분류하여 재배열하는 문제이다.
이는 Stable Sort(기존 상대적 순서 유지)를 만족해야 하므로, 단순한 정렬 알고리즘보다 적절한 방법을 선택해야 한다.

 

인덱스 기반 배열 조작 (O(N) 시간, O(N) 공간)

• 리스트 대신 배열을 사용하여 공간 사용을 줄이는 방법
• left는 pivot보다 작은 값을, right는 pivot보다 큰 값을 저장할 위치

 

> java

 

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        int[] result = new int[nums.length];
        int left = 0, right = nums.length - 1;
        
        for (int i = 0, j = nums.length - 1; i < nums.length; i++, j--) {
            if (nums[i] < pivot) {
                result[left] = nums[i];
                left++;
            }
            
            if (nums[j] > pivot) {
                result[right] = nums[j];
                right--;
            }
        }
        
        while (left <= right) {
            result[left] = pivot;
            left++;
        }
        
        return result;
    }
}

 

 

> python

 

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        n = len(nums)
        left = 0
        right = n-1

        rs = [0] * n
        for i in range(0, len(nums)) :
            if nums[i] < pivot :
                rs[left] = nums[i]
                left+=1
        for i in range(n-1, -1, -1) :
            if nums[i] > pivot :
                rs[right] = nums[i]
                right-=1
        while left <= right :
            rs[left] = pivot
            left+=1
        
        return rs