#문제
11286번: 절댓값 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0�
www.acmicpc.net
#풀이
이 문제는 최소힙을 변형한 문제이다. 처음에 최소힙문제에서 비교부분만 abs()를 씌워서 해결하면 되는 줄 알았지만 그렇게 쉽게 해결되지 않았다. 절댓값 힙은 기본적으로 절댓값이 작은 원소일수록 위에 있지만, 절댓값이 같고 부호가 다르면 음수인 값이 위에 있어야 한다. push후 재정렬과 pop후 재정렬 중에서도 마지막에 좌측자식노드만 있는 경우는 형제 노드를 고려할 필요가 없어서 최소힙 코드에서 약간의 변화를 통해 수정이 가능했지만, pop후 재정렬에서 형제 노드를 고려할 때가 상당히 골치 아팠다. 직접 트리를 그려 어떤 경우의 수가 존재하는지 파악한 후 코드를 작성해 문제를 해결했다.
#소스코드
|
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include<iostream>
using namespace std;
void pop();
void push(int num);
int arr[100005];//index 1부터 사용하니까
int n = 0;//힙에 들어있는 원소의 수
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int testnum = 0;
int num = 0;
cin >> testnum;
for (int i = 0; i < testnum; i++) {
cin >> num;
if (num == 0) {
pop();
}
else {
push(num);
}
}
}
void pop() {
if (n == 0) {
cout << 0 << "\n";
return;
}
else {
cout << arr[1] << "\n";
arr[1] = arr[n];
n--;
//재정렬(index 1의 값이 변경됨)
if (n != 0) {
int t = 1;
while (t * 2 <= n) {
if (t * 2 == n) {
if (abs(arr[t * 2]) < abs(arr[t])) {
swap(arr[t * 2], arr[t]);
t *= 2;
}
else if ((abs(arr[t * 2]) == abs(arr[t])) && arr[t * 2] < 0) {
swap(arr[t * 2], arr[t]);
t *= 2;
}
else {
break;
}
}
else {// 이 부분의 경우의 수를 나누는 것이 상당히 복잡
if ((abs(arr[t * 2]) < abs(arr[t * 2 + 1])) && (abs(arr[t * 2]) < abs(arr[t]))) {
swap(arr[t * 2], arr[t]);
t *= 2;
}
else if ((abs(arr[t * 2]) < abs(arr[t * 2 + 1])) && (abs(arr[t * 2]) == abs(arr[t])) && (arr[t * 2] < 0)) {
swap(arr[t * 2], arr[t]);
t *= 2;
}
else if ((abs(arr[t * 2]) > abs(arr[t * 2 + 1])) && (abs(arr[t * 2 + 1]) < abs(arr[t]))) {
swap(arr[t * 2 + 1], arr[t]);
t = t * 2 + 1;
}
else if ((abs(arr[t * 2]) > abs(arr[t * 2 + 1])) && (abs(arr[t * 2 + 1]) == abs(arr[t])) && (arr[t * 2 + 1] < 0)) {
swap(arr[t * 2 + 1], arr[t]);
t = t * 2 + 1;
}
else if ((abs(arr[t * 2]) == abs(arr[t * 2 + 1])) && (abs(arr[t * 2 + 1]) < abs(arr[t]))) {
if (arr[t * 2 + 1] < arr[t * 2]) {
swap(arr[t * 2 + 1], arr[t]);
t = t * 2 + 1;
}
else{//arr[t*2+1] == arr[t*2]일 때는 어느쪽을 바꿔도 상관없으므로 이 경우에 포함
swap(arr[t * 2], arr[t]);
t = t * 2;
}
}
else if ((abs(arr[t * 2]) == abs(arr[t * 2 + 1])) && (abs(arr[t * 2 + 1]) == abs(arr[t])) && arr[t] > 0) {
//절댓값이 모두 같을 때 arr[t] > 0이어야만 swap해줘야하는 경우가 생긴다.
if (arr[t * 2 + 1] < arr[t * 2]) {
swap(arr[t * 2 + 1], arr[t]);
t = t * 2 + 1;
}
else {//arr[t*2] == arr[t*2+1]일 때는 어느쪽을 바꿔도 상관없으므로 이 경우에 포함
swap(arr[t * 2], arr[t]);
t = t * 2;
}
}
else {
break;
}
}
}
}
}
}
void push(int num) {
n++;
arr[n] = num;
//재정렬(index n의 값이 변경됨)
int t = n;
while (t != 1) {
if (abs(arr[t / 2]) > abs(arr[t])) {
swap(arr[t / 2], arr[t]);
t /= 2;
}
else if ((abs(arr[t / 2]) == abs(arr[t])) && arr[t] < 0) {
swap(arr[t / 2], arr[t]);
t /= 2;
}
else {
break;
}
}
}
|
cs |
'Algorithm > Data Structure' 카테고리의 다른 글
| [C++] 백준 1927번 : 최소 힙 (S1) &11279번 : 최대 힙 (S2) (0) | 2020.10.14 |
|---|