SW사관학교 정글 TIL (10/27)

pintOS 주차가 끝나고 알고리즘 주차를 진행중입니다.

215. Kth Largest Element in an Array

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

sort로 가볍게 넘어갈 수 있는 문제지만 다른 접근법을 찾아봤습니다.

1. sort
2. priority queue
3. quick select

import heapq

class Solution:
    def using_sort(self, nums: List[int], k: int) -> int:
        nums.sort()

        return nums[-k]


    def quick_select(self, nums: List[int], k: int) -> int:
        k = len(nums) - k

        def quick_select(left, right):
            pivot, p = nums[right], left

            # pivot보다 작거나 같은 값들을 왼쪽으로 밀어넣는다
            for i in range(left, right):
                if nums[i] <= pivot:
                    nums[p], nums[i] = nums[i], nums[p]
                    p += 1

            # pivot으로 사용된 값이 중간에 위치하도록 p의 위치로 옮긴다.
            nums[p], nums[right] = nums[right], nums[p]

            if p > k:
                return quick_select(left, p - 1)
            elif p < k:
                return quick_select(p + 1, right)
            else:
                return nums[p]

        return quick_select(0, len(nums) - 1)
    

    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        return heapq.nlargest(k, nums)[-1]

1. sort
   내장함수를 활용하여 정렬한 뒤 뒤에서 k번째 값을 뽑아내면 됩니다.

2. priority queue
   heapq 모듈을 사용해서 nums를 heapify한뒤 k번째 뽑아내는 값이 답이 됩니다.

3. quick select
   quick sort의 응용방식이라고 배웠습니다.

   pivot을 설정하고 그보다 작은 값을 왼쪽으로 몰아넣습니다.
   왼쪽으로 몰아넣은 값 바로 다음에 pivot이 위치하도록 값을 옮겨 준 뒤

   인덱스로 사용했던 값을 k와 비교해 왼쪽 or 오른쪽에서 다시 quick select를 진행해줍니다.
   - 이 문제에서는 시간초과가 나면서 테스트를 통과하지 못합니다.