.leetcode(215. Kth Largest Element in an Array)

문제

https://leetcode.com/problems/kth-largest-element-in-an-array/

문제 풀기 전

1. k-th 이제 익숙하다. 일단 PriorityQueue가 바로 떠올랐다.
2. 단순 array이기에 Arrays.sort로 해도 풀리겠다고도 생각했다.
3. "347. Top K Frequent Elements"에서 배운 Lomuto's Partition을 구현해 볼 기회였다.

직접 푼 풀이

소요시간: 3분(21:55 ~ 21:58, PriorityQueue이용한 풀이), 2분(22:00 ~ 22:02, Arrays.sort 이용한 풀이), 28분(22:02 ~ 22:30, Lomuto's Partition 이용한 풀이)

# PriorityQueue 이용한 풀이
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a,b) -> a - b);

        for (int each: nums) {
            pq.add(each);
            if (pq.size() > k) pq.poll();
        }

        return pq.poll();
    }
}

# Arrays.sort 이용한 풀이
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);

        return nums[nums.length - k];
    }
}

#Lomuto's Partition 이용한 풀이
class Solution {
    public int findKthLargest(int[] nums, int k) {
        sort(nums, 0, nums.length-1);

        return nums[nums.length - k];
    }

    private void sort(int[] nums, int s, int e) {
        if (s >= e) {
            return;
        }

        int pivot = nums[e];

        int left=s;
        int right=s;
        for (int i=s; i<e; i++) {
            if (nums[i] < pivot) {
                //left
                if (i!= left && i > right) {
                    swap(nums, i, left);
                    right = i;
                }
                left++;
            } else {
                //right
                right=i;
            }
        }
        swap(nums, left, e);

        sort(nums, s, left-1);
        sort(nums, left+1, e);
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

느낀점

1. PriorityQueue이용한 건 사실 보통 트리에서 많이 썼었는데 적용하면서 PriorityQueue에 Generic선언을 안한 부분, a-b인지, b-a인지 헷갈린 부분, poll메소드부분이 조금 헷갈렸다.
2. 정렬은 생각할것도 없이 바로 적용하면 되었다.
3. QuickSort을 이번에 처음 제대로 구현해보았다. 일전에 공부했듯이 두가지 구현 방법이 있는데 Lomuto가 제일 오른쪽값을 pivot으로 하는 풀이다. 가장 효과적인 코드로 짜진 않았어도 개념적인 부분은 제대로 구현했고 그렇게 하니 답도 잘 나왔다.
4. 솔루션의 신박한 부분은 2가지인데 랜덤하게 pivot을 정했다는 점과 길이 값(k값)을 이용해 쓸데없는 계산을 하지 않았다는 것이다. 근데 정말 속도가 엄청나게 개선되었다. 속도에서 원래는 10퍼 미만이었는데 90퍼까지 올랐다.

솔루션 공부 후 추가로 푼 풀이

#앞의 quicksort에서 k값 추가하고 pivotindex를 랜덤하게 정하도록 했다.
class Solution {
    public int findKthLargest(int[] nums, int k) {
        sort(nums, 0, nums.length-1, k);

        return nums[nums.length - k];
    }

    private void sort(int[] nums, int s, int e, int k) {
        if (s >= e || e < nums.length - k) {
            return;
        }

        int pivotindex = (int)((e-s) *Math.random()) + s;
        swap(nums, e, pivotindex);
        int pivot = nums[e];

        int left=s;
        int right=s;
        for (int i=s; i<=e; i++) {
            if (nums[i] < pivot) {
                //left
                if (i!= left && i > right) {
                    swap(nums, i, left);
                    right = i;
                }
                left++;
            } else {
                //right
                right=i;
            }
        }
        swap(nums, left, e);

        sort(nums, s, left-1, k);
        sort(nums, left+1, e, k);
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)