첫 시도
- Heap이 이진트리로 되어있는 것은 알고 있음
- ArrayList로 트리 구현
- 인덱스를 계산해야하기 떄문에 0번은 사용 x
- 삽입 : list의 마지막에 값 저장, 이후 부모 노드가 더 작을 때 까지 위치 변환 반복
- 삭제 : 1번에 있는 값을 출력, list의 마지막 값을 1번에 저장하고 아래 자식 노드 값을 비교 -> 왼쪽부터 비교 후 오른쪽 값이 있다면 오른쪽도 비교하면서 내려감
해결
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
public static void main(String[] ars) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> list = new ArrayList<>();
list.add(0);
for (int i = 0; i < N; i++) {
int a = Integer.parseInt(br.readLine());
if(a != 0){
list.add(a);
int index = list.size() - 1;
while(index > 1 && list.get(index/2) > a){
int parent = list.get(index/2);
list.set(index/2,a);
list.set(index,parent);
index /= 2;
}
}
else {
if(list.size() - 1 < 1){
sb.append(0+"\n");
}
else {
int deleteitem = list.get(1);
sb.append(deleteitem + "\n");
list.set(1, list.get(list.size() - 1));
list.remove(list.size() - 1);
int pos = 1;
while ((pos * 2) < list.size()) {
int min = list.get(pos * 2);
int minPos = pos * 2;
if (((pos * 2 + 1) < list.size()) && min > list.get(pos * 2 + 1)) {
min = list.get(pos * 2 + 1);
minPos = pos * 2 + 1;
}
if (min > list.get(pos))
break;
int tmp = list.get(pos);
list.set(pos, list.get(minPos));
list.set(minPos, tmp);
pos = minPos;
}
}
}
}
System.out.println(sb);
}
}