절댓값 힙
https://www.acmicpc.net/problem/11286
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 34334 | 19057 | 15496 | 56.292% |
문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다.
다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.
만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고,
x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
입력되는 정수는 -231보다 크고, 231보다 작다.
예제 입력 1
18 1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0
예제 출력 1
-1 1 0 -1 -1 1 1 -2 2 0
출처
- 문제를 만든 사람: baekjoon
- 잘못된 조건을 찾은 사람: dkim
- 데이터를 추가한 사람: nova9128
- 문제의 오타를 찾은 사람: sgchoi5, youngminz, zerozero
비슷한 문제
알고리즘 분류
priority_queue의 성질을 이용하여 해결하였다.
아래의 자료구조만 이해한다면 쉽게 해결할 수 있는 문제
https://chanhuiseok.github.io/posts/algo-54/ <- 해당 사이트에서 정독하면 쉽게 이해가능합니다.
![](https://lycos7560.com/wp-content/uploads/2023/02/image-50.png)
![](https://lycos7560.com/wp-content/uploads/2023/02/image-52.png)
통과된 코드
#include <iostream> #include <cmath> #include <queue> using namespace std; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myPQ; pair<int, int> tempP; int N, tempO, tempT; int main() { ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화 // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다. cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 0; i < N; i++) { cin >> tempO; if (tempO == 0) { if (myPQ.empty()) cout << 0 << "\n"; else { tempP = myPQ.top(); cout << tempP.first * tempP.second << "\n"; myPQ.pop(); } continue; } if (tempO > 0) tempT = 1; // 나중에 출력을 쉽게 하기 위해서 1로 만들어준다. else tempT = -1; // 나중에 출력을 쉽게 하기 위해서 -1로 만들어준다. myPQ.push(make_pair(abs(tempO), tempT)); } return 0; }
![](https://lycos7560.com/wp-content/uploads/2023/02/image-49.png)