[백준/BOJ] 11920 버블 정렬 (c++)

[백준/BOJ] 11920 버블 정렬 (c++)

11920번: 버블 정렬

 

2025.02.17 - [Competitive Programming] - 02. 정렬 (Sorting Theory) (1. bubble sort)

정렬 (Sorting Theory) (1. bubble sort)

---

버블 정렬 과정에서 버블 정렬의 round가 K번 진행되었을때의 배열 상태를 출력하는 문제입니다.

input size가 10만이므로 O(NK) 시간복잡도를 갖는 버블 정렬을 시뮬레이션 할 수는 없습니다.

 

우선, 오름차순으로 정렬하는 k번의 round가 진행된다면, k개의 큰 수는 정렬된 상태입니다.

 

그 외에 잘못 배치되어 있던 큰 수들은 자신보다 큰 수 k개를 만나기 전까지 우측으로 이동합니다.

 

만약 { 9 8 7 6 5 4 } 와 같은 수열이 있고 k가 3이라면 k round까지는 앞에서 부터 큰 수 k개인 { 9 8 7 } 외에는 swap이 발생하지 않습니다.

또, { 6 5 9 8 7 4 } 와 같은 수열이 있고 k가 3이라면 6은 큰 수 3개를 만나기 전인 5와는 swap이 됩니다. 

 

그러므로 Min Heap을 이용해 현재 위치까지의 k개의 큰 수를 유지한다면,

해당 위치에서 k round까지 swap이 가능한 숫자들을 알 수 있습니다.

 

배열을 순회하면서 우선순위 큐 삽입, 삭제(logN) 연산만 진행하므로 O(NlogN)에 해결할 수 있습니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N, K, a[100000];
priority_queue<int, vector<int>, greater<int>> pq;
int solve() {
    REP(i, 0, N) {
        if (pq.size() < K) {
            pq.push(a[i]);
        } else {
            if (pq.top() < a[i]) {
                cout << pq.top() << " ";
                pq.pop();
                pq.push(a[i]);
            } else {
                cout << a[i] << " ";
            }
        }
    }
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    REP(i, 0, N) {
        cin >> a[i];
    }
    solve();
    return 0;
}