반응형

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

 

1655번: 가운데를 말해요

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

 

왼쪽, 오른쪽으로 나눠서 숫자 삽입
● 오름차순 정렬 기준                                             (1 2 3 4 5 6 7 8 9 10)
    ① 왼쪽   -> 제일 큰 값이 중간값  (max_pq)         1  2 3 4 5 | 6 7 8 9  10
    ② 오른쪽 -> 제일 작은 값이 중간값  (min_pq)

1. 왼쪽, 오른쪽 번갈아가면서 삽입 (왼쪽 먼저)

2. 항상 왼쪽 숫자 <= 오른쪽 숫자 (오름차순 정렬이기 때문)
   if 왼쪽 숫자 > 오른쪽 숫자: 교환

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
// 참고: https://gpfatp.blogspot.com/2019/07/boj-1655.html
#include <iostream>
#include <queue>
using namespace std;
int n, x;
priority_queue<int> left_max_pq;
priority_queue<int, vector<int>, greater<int> > right_min_pq;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    while (n--) {
        cin >> x;
        
        // 왼쪽, 오른쪽으로 나눠서 숫자 삽입
        // ● 오름차순 정렬 기준                        (1 2 3 4 5 6 7 8 9 10)
        // 왼쪽   -> 제일 큰 값이 중간값     (max_pq)    1  2 3 4 "5" | "6" 7 8 9  10
        // 오른쪽 -> 제일 작은 값이 중간값     (min_pq)
 
        // 1. 왼쪽, 오른쪽 번갈아가면서 삽입 (왼쪽 먼저)
        if (left_max_pq.size() == right_min_pq.size())
            left_max_pq.push(x);
        else
            right_min_pq.push(x);
 
        // 2. 오른쪽 숫자가 왼쪽 숫자보다 항상 커야함 (같아도 됨)
        // 오름차순 정렬이기 때문
        // 왼쪽 숫자 > 오른쪽 숫자: 바꿔줌
        if (!left_max_pq.empty() && !right_min_pq.empty() && right_min_pq.top() < left_max_pq.top()) {
            int a = left_max_pq.top(); left_max_pq.pop();
            int b = right_min_pq.top(); right_min_pq.pop();
 
            right_min_pq.push(a);
            left_max_pq.push(b);
        }
        cout << left_max_pq.top() << '\n';
    }
}
 
 
 cs
반응형

'백준 > 우선순위큐' 카테고리의 다른 글

백준 11286  (0) 2021.01.26
반응형

www.acmicpc.net/problem/11286

방법 1. priority queue 두개 사용 (양수 / 음수)

방법 2. pair<int, int> 사용

방법 3. 정렬을 위한 cmp 구조체 사용

 

1. priority 두개 사용

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
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq_pos;
priority_queue<int> pq_neg;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        if (x == 0) {
            if (pq_pos.empty()) {
                // 1. 둘 다 비었음
                if (pq_neg.empty())
                    cout << 0 << '\n';
 
                // 2. 양수pq (x), 음수pq(o)
                else {
                    cout << pq_neg.top() << '\n';
                    pq_neg.pop();
                }
            }
            else {
                // 3. 양수pq (o), 음수pq(x)
                if (pq_neg.empty()) {
                    cout << pq_pos.top() << '\n';
                    pq_pos.pop();
                }
                // 4. 둘 다 있음
                else {
                    if (pq_pos.top() < -pq_neg.top()) {        // 2 vs -3: 양수 출력
                        cout << pq_pos.top() << '\n';        // 2 vs -2: 음수 출력
                        pq_pos.pop();                        // 2 vs -1: 음수 출력
                    }
                    else {
                        cout << pq_neg.top() << '\n';
                        pq_neg.pop();
                     }
                }
            }
        }
        else {
            if (x > 0)
                pq_pos.push(x);
            else
                pq_neg.push(x);
        }
    }
}
 cs

 

2. pair<int, int> 사용

정렬 기준

1순위: 첫 번째 (절대값)

2순위: 두 번째 (원래값)

 

(2, -2)       (1, -1)

(1, -1)       (1, 1)

(1, 1)    -> (2, -2)

(2, 2)        (2, 2)

 

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
#include <iostream>
#include <queue>
#define pii pair<int, int>
using namespace std;
priority_queue<pii, vector<pii>, greater<pii> > pq;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        if (x == 0) {
            if (pq.empty())
                cout << 0 << '\n';
            else {
                cout << pq.top().second << '\n';
                pq.pop();
            }
        }
        else {
            pq.push({ abs(x), x });
        }
    }
}
 cs

 

3. 정렬을 위한 cmp 구조체 사용

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
#include <iostream>
#include <queue>
using namespace std;
struct cmp {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b))
            return a > b;
        return abs(a) > abs(b);
    }
};
priority_queue<int, vector<int>, cmp > pq;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        if (x == 0) {
            if (pq.empty())    
                cout << 0 << '\n';
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
        else {
            pq.push(x);
        }
    }
}
cs
반응형

'백준 > 우선순위큐' 카테고리의 다른 글

백준 1655 [복습필수]  (0) 2021.07.11

+ Recent posts

티스토리툴바