96일 (2161. Partition Array According to Given Pivot) pointer

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

• Every element less than pivot appears before every element greater than pivot.
• Every element equal to pivot appears in between the elements less than and greater than pivot.
• The relative order of the elements less than pivot and the elements greater than pivot is maintained.
  • More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. For elements less than pivot, if i < j and nums[i] < pivot and nums[j] < pivot, then pi < pj. Similarly for elements greater than pivot, if i < j and nums[i] > pivot and nums[j] > pivot, then pi < pj.

Return nums after the rearrangement.

 

Example 1:

Input: nums = [9,12,5,10,14,3,10], pivot = 10
Output: [9,5,3,10,10,12,14]
Explanation: 
The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array.
The elements 12 and 14 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.

Example 2:

Input: nums = [-3,4,3,2], pivot = 2
Output: [-3,2,4,3]
Explanation: 
The element -3 is less than the pivot so it is on the left side of the array.
The elements 4 and 3 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.

 

Constraints:

• 1 <= nums.length <= 10^5
• -10^6 <= nums[i] <= 10^6
• pivot equals to an element of nums.

 

- 접근방법

1. nums와 같은 크기의 배열 answer를 초기화한다.

2. nums를 1번 순회하며 pivot보다 작은 값을 찾아 순서대로 answer배열에 넣는다.

3. nums를 1번 순회하며 pivot과 같은 값을 찾아 순서대로 answer배열에 넣는다.

4. nums를 1번 순회하며 pivot보다 큰 값을 찾아 순서대로 answer배열에 넣는다.

 

 

- 코드

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        int idx = 0;
        int[] answer = new int[nums.length]; // 1

        for(int num : nums) { // 2
            if(num < pivot) answer[idx++] = num;
        }
        for(int num : nums) { // 3
            if(num == pivot) answer[idx++] = num;
        }
        for(int num : nums) { // 4
            if(num > pivot) answer[idx++] = num;
        }

        return answer;
    }
}

 

왜 난이도가 미디엄인건지 도저히 이해가 되지않는다. 뭔가 더 좋은 방법이 있겠지 고민한 시간이 훨씬 긴 것 같다..

 

3개의 각 집단은 원래 배열nums 내의 순서가 섞이면 안되므로 무조건 3번 순회해야하기 때문에

for문을 3번 동작시키는 것 이외에 다른 좋은 방법은 떠오르지 않는다.

 

 

 

 

https://leetcode.com/problems/partition-array-according-to-given-pivot/

Partition Array According to Given Pivot - LeetCode