[LeetCode] 215. Kth Largest Element in an Array

안녕하세요!

 

오늘은 LeetCode의 215. Kth Largest Element in an Array 문제를 풀어보겠습니다.

 

이 문제는 주어진 정수 배열에서 k번째로 큰 요소를 찾는 것입니다. 정렬을 하지 않고 찾는 것이 문제의 조건이었습니다.

 

저는 알고리즘 수업시간에 배운 k-select 알고리즘을 적용해서 풀어보고 싶었습니다. 처음 작성했던 코드는 다음과 같습니다.

 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        while len(nums) >= 1:          
            pivot_index = len(nums)//2 

            pivot = nums[pivot_index]
            L = [i for i in nums if i < pivot]
            R = [i for i in nums if i >= pivot]

            if k == len(R):
                return pivot
            elif k < len(R):
                nums = R
            else:
                nums = L
                k -= len(R)

 

위 코드는 nums 배열 안에서 중복된 요소들을 잘 다루지 못했고, 또 배열의 길이가 2인 경우에 적용할 수가 없었습니다.. 수업 자료와 필기를 보면서 다시 한 번 공부를 했고, leetcode에 올라와있는 솔루션을 참고하기도 했습니다. 이후 다음과 같이 코드를 작성해보았습니다.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # k번째로 큰 요소의 인덱스를 계산하여 quickselect 메서드 호출
        return self.quickselect(nums, len(nums) - k, 0, len(nums) - 1)

    def quickselect(self, nums: List[int], k: int, left: int, right: int) -> int:
        # 피벗을 랜덤으로 선택
        pivot_index = randint(left, right)
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        pivot = right  # 피벗을 오른쪽 요소로 설정
        i, j = left, right - 1  # 왼쪽과 오른쪽 인덱스 초기화

        # 파티션 과정
        while i <= j:
            if nums[i] < nums[pivot]:  # 피벗보다 작은 값
                i += 1
            else:
                if nums[j] > nums[pivot]:  # 피벗보다 큰 값
                    j -= 1
                else:
                    nums[i], nums[j] = nums[j], nums[i]  # 두 값 교환
                    i += 1
                    j -= 1

        # 피벗을 제자리로 이동
        nums[i], nums[pivot] = nums[pivot], nums[i]

        # k와 피벗의 위치 비교
        if i > k:  # 왼쪽 탐색
            return self.quickselect(nums, k, left, i - 1)
        elif i < k:  # 오른쪽 탐색
            return self.quickselect(nums, k, i + 1, right)
        else:  # k번째 요소 반환
            return nums[k]

 

 

heapq를 사용하면 더 빠르게 풀 수 있다고 하던데 일단 저는 최대한 수업시간에 배운 내용을 적용하는 것을 목표로 풀어보았습니다. 기회가 된다면 다른 방법으로도 풀어봐야겠습니다.

 

이 문제를 꽤 오랜 시간 고민을 했었습니다... 고민하면서 아 이 과정을 즐겨야 코딩으로 돈을 벌어먹고 살 수 있는건가 하는 생각이 들어 진로 고민이 더 커졌습니다..