문제

정렬되지 않은 int형 배열 nums가 주어졌을 때 k번째로 큰 원소를 찾는 문제다. 단, k번째로 큰 원소는 유일한 값이 아닐 수 있으며 정렬을 사용하지 않고 풀어야한다.

첫번째 풀이

정렬을 사용하지 않고 가장 k번째 큰 원소를 찾는 방법으로 가장 효율적인 방법은 Heap을 사용하는 것이다. 2중 반복문을 사용해 각 원소가 몇번째로 큰지 확인할 수 있지만 시간복잡도가 $O(n^2)$으로 효율성이 매우 떨어진다. Heap은 데이터 삽입과 삭제에 $O(logN)$으로 효율적인 시간복잡도를 갖는다.

Heap은 가장 크거나 작은 몇개의 원소를 구할때 좋은 자료구조이다.

따라서 Heap을 사용해 풀이했다. Java에서는 내부적으로 Heap을 사용하는 PriorityQueue를 사용할 수 있지만 이번엔 직접 구현해 풀었다.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        MaxHeap maxHeap = new MaxHeap();

        for (int n : nums) {
            maxHeap.add(n);
        }

        int answer = 0;
        while (k-- > 0) {
            answer = maxHeap.poll();
        }

        return answer;
    }

    private class MaxHeap {

        private Integer[] heap = new Integer[100001];
        private int size = 0;

        public void add(int elem) {
            int idx = ++size;
            heap[idx] = elem;

            while (idx > 1 && heap[idx / 2] < heap[idx]) {
                swap(idx / 2, idx);
                idx /= 2;
            }
        }

        public Integer poll() {
            if (size == 0) {
                return null;
            }

            int idx = 1;
            int ret = heap[idx];
            heap[idx] = heap[size--];

            int halfSize = size / 2;
            while (idx <= halfSize) {
                int left = idx * 2;
                int right = idx * 2 + 1;

                if (heap[idx] > heap[left] && heap[idx] > heap[right]) {
                    break;
                } else if (heap[left] < heap[right]) {
                    swap(idx, right);
                    idx = right;
                } else {
                    swap(idx, left);
                    idx = left;
                }
            }

            return ret;
        }

        private void swap(int idx1, int idx2) {
            int temp = heap[idx1];
            heap[idx1] = heap[idx2];
            heap[idx2] = temp;
        }
    }
}

실행결과 실행시간과 메모리 사용량이 하위권으로 나왔다. 메모리 사용량 같은 경우 배열을 동적으로 늘리지 않고 처음부터 최대로 들어갈 수 있는 $10^5$으로 선언했기 때문에 높게 나왔을 가능성이 있다. 내가 구현한 Heap과 비교하기 위해 Java에서 제공하는 PriorityQueue로 제출해보았다. 결과는 다음과 같다.

실행시간도 줄었을 뿐만아니라 메모리 사용량도 개선이 많이 되었다. PriorityQueue는 내부적으로 배열을 사용하는 것은 동일하지만 동적으로 배열을 늘리기 때문에 메모리 사용량이 더 적은 것이라고 생각된다.

PQ로 작성한 코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int n : nums) {
            pq.offer(n);
        }

        while (k-- > 1) {
            pq.poll();
        }

        return pq.poll();
    }
}

두번째 풀이

Java에서 제공하는 PriorityQueue를 사용해도 좋은 결과를 얻을 수 없었다. 문제에서는 정렬을 사용하지 않고 풀라고 했지만 정렬을 사용해 풀어보았다. Arrays.sort()를 이용했으며 Dual-Pivot Quicksort를 사용하며 $O(n\,log\,n)$의 시간복잡도를 갖는다.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

정렬을 이용한 방법이 가장 빠른 실행속도를 얻을 수 있었다.

다른 Solution을 찾아 봤을 때도 이 문제에 가장 효율이 좋은 것은 Quicksort를 사용한 방법이었다.