개요
-
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. -
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
접근 방식
-
최대 힙 문제와 백준 11279번: 최대 힙 동일하게 구조를 짠 뒤 부호 순서만 바꿔줬다.
-
주의해야 할 점은 최대힙에서의 heapify함수에선 왼쪽 자식 체크 후, 오른쪽 자식
체크 할때 초기값(-1)과 같은지 체크할 필요가 없었지만(모든 값이 -1보다 커서)
최소힙에선 -1값이 제일 작아서 루트로 들어가버릴 가능성이 생기므로,
-1이 아닌지 체크해야한다.
전체 코드
#include<iostream>
using namespace std;
//minHeap
class Priority_Queue {
private:
//값이 저장될 배열 index 1부터 시작
int* pq;
//큐안의 원소 갯수, 마지막 원소가 들어있는 인덱스로 사용
int size;
public:
Priority_Queue(int n) {
pq = new int[n];
size = 0;
fill(&pq[0], &pq[n], -1);
}
void Push(int x);
void Pop();
void Heapify(int curIdx);
};
void Priority_Queue::Push(int x) {
//비어있을 경우
if (pq[1] == -1) {
pq[1] = x;
size = 1;
return;
}
//배열의 마지막 원소 다음 index
int cur_idx = ++size;
//배열의 마지막 칸에 x를 넣어준다.
pq[cur_idx] = x;
//방금 들어온 원소 x를 min_heap에 따라 맞는 위치에 넣어주기
while (1) {
//현재 idx가 루트 노드라면 return
if (cur_idx / 2 == 0) return;
//부모 노드가 자식 노드값보다 크다면
if (pq[cur_idx / 2] > pq[cur_idx]) {
//바꿔주기
swap(pq[cur_idx / 2], pq[cur_idx]);
cur_idx /= 2;
}
else
break;
}
return;
}
void Priority_Queue::Pop() {
//비어있다면 0출력
if (pq[1] == -1) {
cout << 0 << '\n';
return;
}
//루트 노드 출력
cout << pq[1] << "\n";
int lastIndex = size--;
//마지막 원소와 루트 노드 바꾸기
swap(pq[1], pq[lastIndex]);
//루트 노드값 제거
pq[lastIndex] = -1;
if (lastIndex != 1)
Heapify(1);
}
/// <summary>
/// pop 후에 루트노드에 박힌 원소값 루트인덱스에서 제자리로 옮겨주는 재귀함수
/// </summary>
/// <param name="curIdx(제자리 찾아가야할 원소의 현재 index)"></param>
void Priority_Queue::Heapify(int curIdx) {
//curIdx가 범위를 벗어나면 리턴
if (curIdx * 2 >= 100'002) return;
//curIdx가 리프노드라면 리턴
if (pq[curIdx * 2] == -1) return;
//임시 인덱스 tmp_idx에 curIdx값 저장(curIdx의 자식 인덱스 가리키는 용도)
int tmp_idx = curIdx;
//tmp_idx 두배 해줌으로 왼쪽 자식 인덱스 가리킴
tmp_idx *= 2;
//왼쪽 자식 오른쪽 자식 비교해 더 작은 값으로 tmp_idx옮김
//maxheap과는 다르게 오른쪽 자식이 -1이라면 -1값을 바꿔버리므로 조심
if ((tmp_idx + 1 <= 100'002) && (pq[tmp_idx + 1] != -1) && (pq[tmp_idx] > pq[tmp_idx + 1]))
tmp_idx++;
//자식중에 더 작은 값보다 현재값이 더 작다면 리턴
if (pq[curIdx] < pq[tmp_idx]) return;
swap(pq[tmp_idx], pq[curIdx]);
Heapify(tmp_idx);
}
void Input() {
//연산이 10만이라했으므로 10만으로 초기화
Priority_Queue* pq = new Priority_Queue(100'002);
int N = 0, tmp = 0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> tmp;
//0 받을시 pop연산
if (tmp == 0) {
pq->Pop();
}
//push연산
else
pq->Push(tmp);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
}
문풀후생
처음에 -1값으로 초기화했더니 틀렸습니다가 뜨고, 0으로 초기화했더니 맞았습니다가 떠서
초기화가 문제인가 이상한 인덱스를 건드리나 체크하다가 시간을 많이 날렸는데,
백준의 어떤 분이 알려주셨는데 line 80에서 100'001번째 인덱스 초과일때 heapify함수를
return걸어야했는데 100'002초과 일때 return을 걸어서
curIdx*2가 100'001부터 값이 들어와서 쓰레기값을 불러서 틀린것이였다.
따라서 100'001 초과일때 return으로 바꾸거나 100'003값으로 배열을 초기화하거나 해야한다.
