본문으로 건너뛰기

2161. Partition Array According to Given Pivot

info

풀이 키워드​

스포주의

구현 투포인터


풀이 코드​

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)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 수준.