👀 문제
https://www.acmicpc.net/problem/1655
👊 도전
1. 설계
- 실시간으로 입력된 데이터를 정렬하는 자료구조->힙(Heap)을 사용한다.
- maxHeap(내림차순), minHeap(오름차순)을 이용한다.
- 두 개를 이용해 정렬된 숫자 배열을 만들 것이다. maxHeap의 리프노드->maxHeap root->minHeap root->minHeap 리프 노드 순으로 가면 정렬된 숫자 배열을 얻을 수 있다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;
import java.io.*;
/**
* @author HEESOO
*
*/
class Main {
public static void main(String[] args) throws IOException {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return i2-i1;
}
}); // 내림차순
PriorityQueue<Integer> minHeap=new PriorityQueue<>((o1, o2)->o1-o2); // 오름차순
for(int i=0;i<n;i++) {
// num을 번갈아가면서 힙에 넣어줌
int num=sc.nextInt();
if(i%2==0) maxHeap.offer(num);
else minHeap.offer(num);
// maxHeap의 root<minHeap root이어야 함
if(!maxHeap.isEmpty() && !minHeap.isEmpty()) {
if(maxHeap.peek()>minHeap.peek()) {
int maxRoot=maxHeap.poll();
maxHeap.offer(minHeap.poll());
minHeap.offer(maxRoot);
}
}
// maxHeap의 root에 숫자 배열의 중간값이 들어감
System.out.println(maxHeap.peek());
}
}
}
3. 결과
🤟 성공 🤟
처음에는 단순하게 리스트를 정렬하고 중간 인덱스를 뽑는 방식으로 작성했는데 시간 초과가 떴다.
리스트를 이용한 코드의 시간 복잡도가 O(N*NlogN)인데, N=10^5이므로 시간이 빠른 편은 아니다.
4. 설명
- 힙을 이용한다
- maxHeap, minHeap 두 개를 사용하여 숫자 배열을 오름차순 정렬할 것이다.
- maxHeap의 leaf node -> maxHeap root -> minHeap root -> minHeap leaf node 순으로 방문하면 숫자 배열을 오름차순 순회하는 것과 같다.
- 따라서 maxHeap root는 minHeap root보다 작아야 한다.
- 두 root 노드가 배열의 중간값이 되고, 중간값이 짝수인 경우 더 작은 값을 택한다고 했으므로 maxHeap root를 리턴하면 된다.
- 따라서 maxHeap, minHeap 순으로 번갈아 숫자를 넣고, 두 root값을 체크하여 조건에 맞지 않는다면 swap하면 된다.
- 참고로, 우선순위 큐에서 Comparator 쓰는 방법은 위 코드와 같이 두 개가 있다.
5. 성능
- 시간 복잡도: O(NlogN)
숫자 개수 N, 힙 정렬 logN -> O(NlogN) - 공간 복잡도: O(N)
👏 해결 완료!
참고
- [BOJ 백준] 가운데를 말해요(1655) Java https://subbak2.tistory.com/19