11286번 - 절댓값 힙
출처: 백준 알고리즘
주소: www.acmicpc.net/problem/11286
11286번: 절댓값 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
문제 요약:
(1) 절댓값이 작은 힙 클래스 생성
=> 힙의 최대 크기(N): 100000, 힙에 저장되는 정수 범위: -231 ~ 231
(2) 0이 아닌 정수를 입력 받으면 힙에 입력
(3) 0을 입력으로 받으면 절댓값이 가장 작은 값 출력하고 그 값을 힙에서 제거
=> 만일 절댓값이 가장 작은 값이 여러 개인 경우, 그 중에 제일 작은 값 하나만 출력하고 제거한다.
문제 해결:
A. 절댓값이 작은 힙 클래스 정의
B. 절댓값이 작은 힙 클래스 내의 삽입 함수 생성
C. 절댓값이 작은 힙 클래스 내의 삭제 함수 생성
알고리즘:
A. 절댓값이 작은 힙 클래스 정의(HeapClass)
1. 클래스 변수(private)
- 힙(heap)을 저장하는 배열 heap 생성
=> 배열의 크기: 100001(인덱스 1부터 저장), 타입: long long int
- heap size를 저장하는 변수 생성(heap_size)
=> 타입: int
2. 클래스 함수(public)
- HeapClass 생성자
=> heap_size를 0으로 초기화
=> 배열 heap을 0으로 초기화
- 입력받은 값(x)을 힙에 저장하는 함수(InputX)
=> 반환값 없음(void), 입력값(x)의 타입: long long int
- 절댓값이 작은 값을 제거하고 출력하는 함수(DeleteX)
=> 반환값(del_val): 절댓값이 작은 값, 반환값의 타입: long long int, 입력값 없음
- heap_size를 반환하는 함수(HeapSize)
=> 반환값: int, 입력값 없음
- 배열 heap을 출력하는 함수(PrintX)
=> 반환값 없음, 입력값 없음
A. 소스 코드:
|
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
|
#include <iostream>
#define MAX_HEAP_LEN 100001
class HeapClass {
private:
long long int heap[MAX_HEAP_LEN];
int heap_size;
public:
HeapClass();
void InputX(long long int x);
long long int DeleteX();
void PrintX();
int HeapSize();
};
HeapClass::HeapClass() {
heap_size = 0;
for (int i = 0; i < MAX_HEAP_LEN; i++) {
heap[i] = 0;
}
}
void HeapClass::PrintX() {
printf("heap: ");
for (int i = 1; i <= heap_size; i++) {
printf("%lld ", heap[i]);
}
printf("\b\n");
}
int HeapClass::HeapSize() {
return heap_size;
}
|
cs |
B. 절댓값이 작은 힙 클래스 내의 삽입 함수 생성(InputX)
1. x값을 넣는 위치 인덱스(x_idx) 선언
2. heap_size 1 증가
3. x_idx에 heap_size 대입
4. x_idx가 1이 아니면 반복
4-1. (x의 절대값 > x_idx의 부모 노드의 절대값) 이면 break;
4-2. (x의 절대값 == x_idx의 부모 노드의 절대값)
&& (x >= x_idx의 부모 노드의 값) 이면 break;
4-3. x_idx의 노드 값에 x_idx의 부모 노드 값 대입
4-4. x_idx를 x_idx 부모 노드의 인덱스 값으로 갱신
5. heap에서 x_idx에 입력값(x) 대입
B. 소스 코드:
|
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
|
void HeapClass::InputX(long long int x) {
// x값을 넣는 위치 인덱스
// heap_size보다 1 증가
int x_idx = ++(heap_size);
// 1. x값을 넣는 위치가 1이면 비어있는 힙
// 2. x값의 부모 절대값보다 x값의 절대값이 더 작은 경우
while (x_idx != 1) {
if (abs(x) > abs(heap[x_idx / 2])) {
break;
}
if ((abs(x) == abs(heap[x_idx / 2]))
&& (x >= heap[x_idx / 2])) {
break;
}
// x 위치에 부모 노드 값 대입
heap[x_idx] = heap[x_idx / 2];
// x위치를 부모 위치로 이동
x_idx /= 2;
}
// 최종 x 위치에 x 대입
heap[x_idx] = x;
}
|
cs |
C. 절댓값이 작은 힙 클래스 내의 삭제 함수 생성(DeleteX)
1. 힙의 마지막 값(last_val), 삭제할 값(del_val) 선언
2. 자식 노드 인덱스(child_idx)와 부모 노드 인덱스(parent_idx) 선언
3. 선언한 변수에 값 대입
4. (child_idx <= heap_size) 이면 반복
4-1. (child_idx < heap_size) && (왼쪽 자식 노드의 절대값 > 오른쪽 자식 노드의 절대값) 이면 child_idx을 1 증가
4-2. (child_idx < heap_size) && (왼쪽 자식 노드의 절대값 == 오른쪽 자식 노드의 절대값)
&& (왼쪽 자식 노드 > 오른쪽 자식 노드) 이면 child_idx을 1 증가
4-3. (last_val의 절대값 < 자식 노드의 절대값) 이면 break;
4-4. (last_val의 절대값 == 자식 노드의 절대값) && (last_val < 자식 노드의 값) 이면 break;
4-5. 부모 노드에 자식 노드를 대입
4-6. parent_idx와 child_idx 갱신
5. heap에서 parent_idx에 last_val 대입
6. del_val 리턴
C. 소스 코드:
|
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
|
long long int HeapClass::DeleteX() {
// 삭제할 값과 마지막 값
// 자식 노드 인덱스와 부모 노드 인덱스
long long int last_val, del_val;
int child_idx, parent_idx;
// 대입
last_val = heap[(heap_size)--];
del_val = heap[1];
child_idx = 2;
parent_idx = 1;
while (child_idx <= heap_size) {
// 1. child_idx가 heap_size보다 작은 경우
// 2. 왼쪽 자식 노드의 절대값 > 오른쪽 자식 노드의 절대값
if ( (child_idx < heap_size) && (abs(heap[child_idx]) > abs(heap[child_idx + 1]))) {
child_idx++;
}
// 1. child_idx가 heap_size보다 작은 경우
// 2. 왼쪽 자식 노드의 절대값 == 오른쪽 자식 노드의 절대값
// 3. 왼쪽 자식 노드 > 오른쪽 자식 노드
else if ((child_idx < heap_size) && (abs(heap[child_idx]) == abs(heap[child_idx + 1]))
&& (heap[child_idx] > heap[child_idx + 1])) {
child_idx++;
}
// 마지막 값의 절대값 < 자식 노드의 절대값
if ( abs(last_val) < abs(heap[child_idx]) ) {
break;
}
// (마지막 값의 절대값 == 자식 노드의 절대값) && (마지막 값 < 자식 노드의 값)
if ((abs(last_val) == abs(heap[child_idx])) && (last_val < heap[child_idx])) {
break;
}
heap[parent_idx] = heap[child_idx];
parent_idx = child_idx;
child_idx *= 2;
}
heap[parent_idx] = last_val;
return del_val;
}
|
cs |
소스 코드(전체 코드):
|
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
125
126
127
128
129
130
131
132
133
134
135
136
|
#include <iostream>
#define MAX_HEAP_LEN 100001
class HeapClass {
private:
long long int heap[MAX_HEAP_LEN];
int heap_size;
public:
HeapClass();
void InputX(long long int x);
long long int DeleteX();
void PrintX();
int HeapSize();
};
HeapClass::HeapClass() {
heap_size = 0;
for (int i = 0; i < MAX_HEAP_LEN; i++) {
heap[i] = 0;
}
}
void HeapClass::PrintX() {
printf("heap: ");
for (int i = 1; i <= heap_size; i++) {
printf("%lld ", heap[i]);
}
printf("\b\n");
}
int HeapClass::HeapSize() {
return heap_size;
}
void HeapClass::InputX(long long int x) {
// x값을 넣는 위치 인덱스
// heap_size보다 1 증가
int x_idx = ++(heap_size);
// 1. x값을 넣는 위치가 1이면 비어있는 힙
// 2. x값의 부모 절대값보다 x값의 절대값이 더 작은 경우
while (x_idx != 1) {
if (abs(x) > abs(heap[x_idx / 2])) {
break;
}
if ((abs(x) == abs(heap[x_idx / 2]))
&& (x >= heap[x_idx / 2])) {
break;
}
// x 위치에 부모 노드 값 대입
heap[x_idx] = heap[x_idx / 2];
// x위치를 부모 위치로 이동
x_idx /= 2;
}
// 최종 x 위치에 x 대입
heap[x_idx] = x;
}
long long int HeapClass::DeleteX() {
// 삭제할 값과 마지막 값
// 자식 노드 인덱스와 부모 노드 인덱스
long long int last_val, del_val;
int child_idx, parent_idx;
// 대입
last_val = heap[(heap_size)--];
del_val = heap[1];
child_idx = 2;
parent_idx = 1;
while (child_idx <= heap_size) {
// 1. child_idx가 heap_size보다 작은 경우
// 2. 왼쪽 자식 노드의 절대값 > 오른쪽 자식 노드의 절대값
if ( (child_idx < heap_size) && (abs(heap[child_idx]) > abs(heap[child_idx + 1]))) {
child_idx++;
}
// 1. child_idx가 heap_size보다 작은 경우
// 2. 왼쪽 자식 노드의 절대값 == 오른쪽 자식 노드의 절대값
// 3. 왼쪽 자식 노드 > 오른쪽 자식 노드
else if ((child_idx < heap_size) && (abs(heap[child_idx]) == abs(heap[child_idx + 1]))
&& (heap[child_idx] > heap[child_idx + 1])) {
child_idx++;
}
// 마지막 값 < 자식 노드
if ( abs(last_val) < abs(heap[child_idx]) ) {
break;
}
if ((abs(last_val) == abs(heap[child_idx])) && (last_val < heap[child_idx])) {
break;
}
heap[parent_idx] = heap[child_idx];
parent_idx = child_idx;
child_idx *= 2;
}
heap[parent_idx] = last_val;
return del_val;
}
int main() {
// 변수 선언
int n;
long long int x, min_val;
HeapClass h;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &x);
if (x != 0) {
h.InputX(x);
}
else {
if (h.HeapSize() > 0) {
min_val = h.DeleteX();
printf("%lld\n", min_val);
}
else {
printf("%d\n", 0);
}
}
}
return 0;
}
|
cs |
한줄평:
-> 힙을 생성할 때의 조건을 여러가지 넣을 수도 있다.