알고리즘
백준 - 절대값힙(11286)
SniKuz
2023. 5. 3. 22:45
링크 : https://www.acmicpc.net/status?user_id=sniz&problem_id=11286&from_mine=1
문제 설명
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
- 배열에 정수 x (x ≠ 0)를 넣는다.
- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
제한조건
총 N개의 연산이 이루어진다. (1<= N <= 100,000). 연산에는 정수 x가 주어지고, x가 0이 아니라면 힙에 넣고, x가 0이라면 배열에서 절댓값 중 가장 작은 값을 출력한다. 정수는 +- 2^31 범위 내에 존재한다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int ans = 0;
int N;
cin >> N;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
//<절대값, 기존값>(0보다 작으면 음수)> 음수면 - 붙여서 내보내줌
while(N > 0)
{
N--;
int tmp;
cin >> tmp;
if(tmp == 0)
{
if(pq.empty())
{
cout << 0 << '\n';
}
else
{
cout << pq.top().second << '\n';
pq.pop();
}
}
else
{
if (tmp < 0)
{
pq.push({-tmp, tmp});
}
else
{
pq.push({tmp, tmp});
}
}
}
system("pause > nul");
return 0;
}
아이디어
힙에 넣을 때, 절대값과 원본값을 세트로 넣어, 절대값에 대해 힙을 하고, 만약 절대값이 같다면 원본값에 대해 힙이 이루어지도록 작성한다.
다른 방법으로 구조체나 클래스로 절대값, 음수인 개수, 양수인 개수 추가한 후 배열에 넣어 유지해주는 방식이나 다른 방식을 생각해보고 적용해봐도 좋을 것 같다.
* greater를 적용하는 방식등을 봤을 때 진짜 정리하기로 마음 먹었었는데... 1시간 씩 정리를 꼭 해야겠다.