정렬되지 않은 배열이 주어졌을 때, 그 배열에서 k번째로 큰 요소를 찾아야 하는 경우가 있습니다. 예를 들어 배열이 [3, 2, 1, 5, 6, 4]이고 k = 2라면, 결과는 두 번째로 큰 값인 5가 됩니다.
해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 배열의 요소들을 오름차순으로 정렬합니다.
- k가 1이면 가장 마지막 요소(최댓값)를 반환하고, 그렇지 않으면 배열의 길이를 n이라 할 때
array[n - k]를 반환합니다.
정렬된 배열에서 k번째로 큰 값은 뒤에서 k번째 위치에 있으므로, 인덱스 n-k에 접근하면 간단히 구할 수 있습니다.
구현 예제
class Solution(object):
def findKthLargest(self, nums, k):
nums.sort()
if k == 1:
return nums[-1]
return nums[len(nums) - k]
ob1 = Solution()
print(ob1.findKthLargest([56,14,7,98,32,12,11,50,45,78,7,5,69], 5))입력
[56,14,7,98,32,12,11,50,45,78,7,5,69] 5
출력
50
코드 설명
위 코드에서 findKthLargest 메서드는 먼저 nums.sort()를 호출하여 배열을 오름차순으로 정렬합니다. 이후 k가 1인 경우 가장 큰 값을 의미하므로 nums[-1](마지막 요소)를 반환하고, 그 외의 경우에는 정렬된 배열의 끝에서 k번째 위치인 nums[len(nums) - k]를 반환합니다.
예제 입력 [56, 14, 7, 98, 32, 12, 11, 50, 45, 78, 7, 5, 69]를 정렬하면 [5, 7, 7, 11, 12, 14, 32, 45, 50, 56, 69, 78, 98]이 되고, 여기서 5번째로 큰 값은 50입니다.
시간 복잡도
이 방법은 정렬에 O(n log n)의 시간이 소요됩니다. 더 효율적인 접근이 필요하다면 힙(Heap) 자료구조나 퀵셀렉트(QuickSelect) 알고리즘을 사용하여 평균 O(n) 시간에 해결할 수도 있습니다.