Container에서 최댓값 (혹은 최솟값)을 찾거나 N번째의 해당 값을 찾는 문제를 푸는 방법
1. Container를 정렬한 후 N번째 혹은 최대(최솟값)을 찾는다.
2. Heap 자료구조를 사용하여 Heap 속성을 유지하는 이진 트리를 만든 후, Root 노드에 접근하여 최댓값 (혹은 최솟값)을 찾거나 N번 Pop을 실행해 원소를 찾는다.
2번의 경우 Container를 정렬하지 않고 시간 복잡도 O(log n)으로 문제를 풀 수 있다. 코딩 문제로도 내기 좋은 문제인듯? 정렬을 쓰지 않아야 하는 조건이 있고, 시간 복잡도도 물어볼 수 있겠다.
2번을 사용하기 위해서는 Heap 자료구조에 대한 이해가 필요하다. 이는 아래 포스팅을 참고하자.
[자료구조] 힙(Heap), 우선 순위 큐
Heap, 힙 힙(heap)은 힙 속성을 만족하는 tree를 기반으로하는 자료구조 이다. 힙 속성은 다음과 같다. A가 B의 부모 노드라면, A 노드의 값은 B 노드의 값과 대소 관계가 성립한다. 이때, 부모 노드가
iridescentboy.tistory.com
위 예시 문제는 Leet Code 215. Kth Largest Element In an Array 문제를 풀어보자.
정렬(Sorting) 없이 Container의 N번째로 큰 원소를 찾는 코드를 구현해야 하는 문제이다.
Kth Largest Element in an Array - LeetCode
Can you solve this real interview question? Kth Largest Element in an Array - Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct eleme
leetcode.com
'개념공부 > 알고리즘' 카테고리의 다른 글
| Sliding Window (슬라이딩 윈도우) TC O(N) Technique (0) | 2023.08.01 |
|---|---|
| 배열에서 연산의 최댓값 혹은 최솟값을 가지는 2개의 값 찾기 문제 (Two Pointers) (0) | 2023.08.01 |
| [자료구조] 힙(Heap), 우선 순위 큐 (0) | 2023.07.30 |
| Interval, Scheduling 문제 (LeetCode 435) (0) | 2023.07.28 |
| Fibonacci(피보나치), Tribonacci 문제 풀이 DP, Recursion, Bottom Up (0) | 2023.07.27 |
