C++ 크리스마스 선물 - 백준 알고리즘
Updated:
14235번 크리스마스 선물
문제
크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.
이제 산타가 선물을 나눠줄 것이다. 차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.
입력
첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)
다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)
5
0
2 3 2
0
0
0
출력
a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.
-1
3
2
-1
정답
#include <iostream>
#include <algorithm>
#include <limits>
#include <cstdio>
using namespace std;
const int MAXN = 250000;
inline int parent(int i) { return (i / 2); } // i도 정수니까 floor 사용하지 않아도 됨
inline int lchild(int i) { return (i * 2); }
inline int rchild(int i) { return (i * 2 + 1); }
const int MIN_KEY = numeric_limits<int>::min();
void max_heapify(int heap[], int i); // 오직 Internal node에만 적용(정렬용도)
int heap_extract_max(int heap[]); // 가장 큰 놈 찾아서 반환
void heap_increase_key(int heap[], int i, int key); // 노드의 값을 바꾸고 정렬
void max_heap_insert(int heap[], int key); // heap에 key를 추가하고 순서 정렬
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N = 0, A = 0;
int max = 0;
int M = 0;
int heap[MAXN +1] = { 0 };
cin >> N; // 방문할 횟수 입력 받음
for (int i = 0; i < N; i++) // N 번 입력 받음
{
cin >> A;
if (A == 0) // 아이를 만났을 때
{
// 선물의 가치를 출력(없으면 -1을 출력)
if (heap[0] > 0)
{
max = heap_extract_max(heap);
cout << max << "\n";
}
else
cout << "-1\n";
}
else // 거점지에 왔을 때
{
for (int j = 0; j < A; j++) // A번 반복하면서 선물의 가치를 입력받아 저장
{
cin >> M;
max_heap_insert(heap, M);
}
}
}
return 0;
}
void max_heapify(int heap[], int i) // 오직 Internal node에만 적용(정렬용도)
{
int left, right, largest;
left = lchild(i); // 왼쪽 아들의 노드 번호
right = rchild(i); // 오른쪽 아들의 노드 번호
largest = i; // 가장 큰놈을 찾기 위해 i를 largest로 설정
if (left <= heap[0] && heap[left] > heap[largest]) // left node 가 존재 && left가 largest보다 클 때
largest = left;
if (right <= heap[0] && heap[right] > heap[largest]) // right node 가 존재 && right가 largest보다 클 때
largest = right;
if (largest != i)
{
swap(heap[i], heap[largest]); // i 와 largest를 swap
max_heapify(heap, largest); // 다시 largest를 i로 넣어서 반복
}
}
int heap_extract_max(int heap[]) // 가장 큰 놈 찾아서 반환
{
int max;
if (heap[0] < 1) // heap의 size가 0일 때 에러 출력(찾을 놈이 없음)
{
printf("heap underflow\n");
exit(1);
}
max = heap[1]; // heap의 가장 큰 놈을 max 로 받음
heap[1] = heap[heap[0]]; // heap의 맨 마지막 단의 값을 가져와 heap[1]에 저장
heap[0]--; // heap의 size를 저장하는 값인 heap[0]의 값을 하나 줄임
max_heapify(heap, 1); // max_heapify를 사용
return max;
}
void heap_increase_key(int heap[], int i, int key)// 노드의 값을 바꾸고 정렬
{
if (key < heap[i]) // 증가시키려는 값보다 작으면 에러 출력
{
printf("new key is smaller than current key\n");
exit(1);
}
heap[i] = key; // 인자로 받은 key값을 heap[i]에 저장
while (i > 1 && heap[parent(i)] < heap[i]) // i가 1보다 크고 아버지 노드가 더 작을 때 실행
{
swap(heap[parent(i)], heap[i]); // heap[i]와 그 아버지 노드의 값을 바꿈
i = parent(i); // i가 아버지 노드의 값이 됨
}
}
void max_heap_insert(int heap[], int key) // heap에 key를 추가하고 순서 정렬
{
heap[0]++; // heap size 하나 늘림
heap[heap[0]] = MIN_KEY; // key 값을 최소값으로 선언(늘린 곳에)
heap_increase_key(heap, heap[0], key); // 거기에 저장하고 순서 정렬
}
STL을 사용하지 않고 직접 max-heap을 구현하여 문제를 풀어봤습니다. 다음 포스팅은 STL에 있는 queue를 사용하여 다른 문제를 풀어보도록 하겠습니다.
Leave a comment