2161. Partition Array According to Given Pivot

info

• 문제 보기: 2161. Partition Array According to Given Pivot
• 소요 시간: 14분 2초
• 풀이 언어: java
• 체감 난이도: 1️⃣~2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

구현 투포인터

풀이 코드

info

• 메모리: 68300 KB
• 시간: 4 ms

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        int[] ans = new int[nums.length];

        int i = 0;
        int j = nums.length-1;
        int ansL = 0;
        int ansR = nums.length-1;
        while (i < nums.length) {
            if (nums[i] < pivot) {
                ans[ansL++] = nums[i];
            }
            if (nums[j] > pivot) {
                ans[ansR--] = nums[j];
            }
            ++i; --j;
        }
        while (ansL <= ansR) {
            ans[ansL++] = pivot;
        }

        return ans;
    }
}

풀이 해설

투포인터를 이용하여, pivot보다 작은 수는 왼쪽부터 i 인덱스로 스캔하며 정답 배열에 넣어주고

pivot보다 큰 수는 오른쪽부터 j 인덱스로 역방향 스캔하며 넣어준다.

스캔이 끝나면 ansL과 ansR 인덱스를 통해 pivot 값을 넣어준다.

시간복잡도는 $O(n)$이다.

info

static 트릭을 통해 런타임 최적화를 할 수 있다. (exploit이며, 패치될 수 있음)

class Solution {
    static{int[] a = {1}; for (int i = 0; i < 100; i++) pivotArray(a, 1);}
    public static int[] pivotArray(int[] nums, int pivot) {
        ...

메모

• 왜 처음 풀때 뒤에꺼 거꾸로 순회할 생각을 못했지?
• 투포인터 의심되면 걍 while문부터 쓰고있자
• Array가 아닌 ArrayList로 구현할 시 꽤 비효율적으로 변한다.
  • 4ms -> 21ms 수준.