반응형

https://www.acmicpc.net/problem/11286

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. struct를 만들어 입력된 수와 절댓값을 저장합니다.

 

2. pq에 절댓값이 낮은 순으로 정렬하고, 같다면 수가 낮은 순으로 정렬합니다.

 

3. 0이 입력되면 pq에서 하나씩 뽑아가면서 출력합니다.

 

[ 소스 코드 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int num;
    int absolute;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (right.absolute == left.absolute) return left.num < right.num;
        return left.absolute < right.absolute;
    }
};
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    int N;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int x;
        scanf("%d", &x);
        if (x != 0) {
            pq.push({ x,abs(x) });
        }
        else {
            if (!pq.empty()) {
                printf("%d\n", pq.top().num);
                pq.pop();
            }
            else {
                printf("%d\n", 0);
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20

+ Recent posts

티스토리툴바