문제
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.
출력
한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.
1. 문제 해석
중간값을 출력하되 매번 입력을 받아 달라지는 중간값을 출력하는 것이다.
매번 그 값이 달라지기 때문에, 입력을 받을 때마다 정렬을 하고 가운데 값을 출력하는 것은
정렬자체가 아무리 빨라도 NlogN 시간이 걸리기 때문에, N^2logN 시간 복잡도를 갖고, 이는 시간초과를 일으키며 효율적이지 못하다.
그래서 여기서는 우선순위 큐를 사용하거나 인덱스 트리를 사용해서 풀이하는 법을 설명하려고 한다.
1. 우선순위 큐와 힙
https://velog.io/@ember/23.-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90%EC%99%80-%ED%9E%99
[우선 순위큐를 잘 설명한 블로그]
여기에서 먼저 우선순위큐에 대한 배경지식을 얻도록 하자.
23. 우선순위 큐와 힙
우선순위 큐, 힙 이론/문제
velog.io
우선순위큐를 이용해서 중간 값을 구할 수 있다.
우선순위큐는 보통 힙으로 구현되어 있다.
최소힙과 최대힙은 각각 루트 노드가 최소부터 정렬되어있고 루트 노드가 최대부터 작은 순으로 정렬되어있는 힙이다.
기본적으로 우리는 작은 값들은 최대힙에 넣고, 큰 값들은 최소 힙에 넣을 것이다.
무슨 말인가 하면,
위의 말처럼 구현해두면
최대힙, 최소힙은 다음과 같은 모양일 것이다.
주의점은 여기서 min 은 최대힙이고 max는 최소힙이다. (작은 값들이 들어가기때문에 min일뿐이다.)
min max
1 [5]
2 6
3 7
[4] 8이렇게 되면 새로운 숫자가 들어왔을 때
작은 값들의 최대 혹은 큰 값들의 최소와 비교해서 어느 힙에 넣을 지 선택을 할 수 있다.
그리고 최대, 최소 힙의 크기가 2이상 차이가 나면 다른 힙으로 보내주면서 그 크기를 유지할 것이다.
(그렇게 해야 중간 값을 찾을 수 있다.)
: 여기에서는 최소힙(max)의 크기가 최대힙(min)보다 큰 경우,
즉 최대힙(min)의 크기가 최소힙(max)이상이거나 1크게 되도록 만든다.
예시를 살펴보도록 하자.
1. 10을 입력받았을 때
min max
1 [5]
2 6
3 7
[4] 8
input << 10
max.top() = 5 < 10
이므로 max에 push
min max
1 [5]
2 6
3 7
[4] 8
102. 20 입력 시
input << 20
min max
1 [5]
2 6
3 7
[4] 8
10
20
max.top() = 5 < 20
이므로 max에 push
{힙의 사이즈 비교}
if min.size() < max.size() {max의 수가 너무 많으므로 min으로 하나를 옮긴다: 가장 작은 5를}
data = max.pop() {5가 pop된다.]
min.push(data) {5가 min에 들어간다.]
결과 :
min max
1 6
2 7
3 8
4 10
[5] 20
이렇게 구현하면 모든 수열에서 중간값은 min의 루트, 즉 최대힙에서 가장 큰 값이 된다. (예시를 자세히 보면 된다)
2. 구현
구현한 코드는 다음과 같다.
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
int N;
vector <int> v;
priority_queue <int> minheap;
priority_queue <int> maxheap;
#define MIN 1
#define MAX 2
/*
수열을 두 개의 힙에 저장하되,
작은 값들은 최대힙에 저장하고 큰 값들은 최소힙에 저장한다.
새로운 값을 넣을 때, 두개의 힙에서 pop한 값을 비교해서 저장하고,
개수가 2개 이상 차이날 때는 pop해서 두개를 바꿔서 넣어준다.
작은 값들이 저장되어있는 최대힙에서 pop해서 출력한다.
maxheap은 최소힙이므로 음수 처리해서 저장하고 꺼내도 부호를 바꾸어주어야한다!
*/
void ft_swap(int flag)
{
int data;
if(flag == MIN)
{
data = minheap.top();
minheap.pop();
maxheap.push(-data);
//printf("swap min to max\n");
}
else
{
data = -maxheap.top();
maxheap.pop();
minheap.push(data);
//printf("swap max to min\n");
}
}
void check_size(int flag)
{
if (minheap.size() < maxheap.size() || minheap.size () > maxheap.size() + 1)
ft_swap(flag);
else
return;
}
void push_heap(int n)
{
//1. heap 사이즈 확인: 두번째 저장해서 min에만 들어있는 경우 대소 비교 후 힙에 저장.
//2. maxheap 의 최소값과 min힙의 최댓값과 n을 비교해서 삽입.
//3. 힙의 개수를 비교한 후 바꿔서 저장.
//printf("max heap size :%d", maxheap.size());
if (maxheap.size() == 0)
{
if (minheap.top() > n) //min 에 들어있는 수보다 더 작은 수가 들어온 경우 자리를 바꾼다.
{
int data = minheap.top();
minheap.pop();
maxheap.push(-data);
minheap.push(n);
//printf("push max %d\n", n);
return;
}
else
maxheap.push(-n);
return;
}
int min = -maxheap.top();
if (n >= min)
{
maxheap.push(-n);
check_size(MAX);
}
else
{
minheap.push(n);
check_size(MIN);
}
}
void input()
{
int n;
for (int i = 0; i < N; i++)
{
cin >> n;
if (i == 0)
minheap.push(n);
else
push_heap(n);
cout << minheap.top() << "\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
input();
}
3. 다른 방법
인덱스 트리로도 구현할 수 있다.
다른 글에 올라올 예정이다1
'알고리즘 > 문제풀이' 카테고리의 다른 글
| 백준 7453 네 수의 합 - 투 포인터 알고리즘 (0) | 2023.01.19 |
|---|---|
| 백준 10250번 - ACM 호텔 (0) | 2023.01.17 |
| 백준 1806: 부분합 (0) | 2023.01.15 |
| 백준 1181번 - 단어 정렬 , c++ sort함수 (5) | 2023.01.09 |
| 백준 2805번: 나무자르기 - 이분탐색 (0) | 2023.01.08 |