🙋♂️ 들어가며
이번 시간에는 PriorityQueue를 배워보자
Q는 FIFO인데, 그와 달리 PQ는 정렬을 통해 오름차순, 내림차순으로도 가능하다
heap 기반으로 시간복잡도는 다음과 같다
1
2
3
| 삽입 (offer) -> O(log N)
삭제 (poll) -> O(log N)
조회 (peek) -> O(1)
|
✅ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PriorityQueue<int[]> pq = new PriorityQueue<> (
(a,b) -> a[0] - b[0]
);
pq.offer(new int[] {3, 100});
pq.offer(new int[] {1, 200});
pq.offer(new int[] {2, 50});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
System.out.println(Arrays.toString(cur));
}
}
}
|
출력값
1
2
3
| [1, 200]
[2, 50]
[3, 100]
|
위처럼 a[0] - b[0] 가 아닌 약간의 변화를 주자
출력값
1
2
3
| [2, 50]
[3, 100]
[1, 200]
|
그렇다면 이번에는 내림차순을 볼까?
앞자리만 바꿔보자
출력값
1
2
3
| [3, 100]
[2, 50]
[1, 200]
|
이번에는 뒷자리를 바꿔보자
출력값
1
2
3
| [1, 200]
[3, 100]
[2, 50]
|
