BOJ 11920 버블 정렬

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/11920

🧐 관찰 및 접근

#

• 배열 $[3, 4, 1, 2, 7, 6]$이 있다고 하자. 처음 한바퀴를 돌면 어떻게 되지?
  • $[3, 1, 2, 4, 6, 7]$이 된다.
    • 이걸 어떻게 해석할 수 있을까?
    • 가장 큰 수는 맨 오른쪽에 고정된다.
    • 다른 수들은, 오른쪽에 붙어있수가 자기보다 작은것들을 왼쪽으로 다 밀고, 오른쪽으로 간다.
      • 오큰수? 스택? 그런맛인데 이거
    • 두번하면 어떻게?
  • $[1, 2, 3, 4, 6, 7]$이 된다.
    • 나 5 안썼었구나 ㅋㅋ 이런
    • 값을 두개정도 들고있다가..? 뭔가 그런느낌…? $K$번 진행한다고 하면, 값을 $K$개정도 들고있다가, 들고있는 값중 젤 작은거보다 작으면 그대로 통과시키고, 그것보다 크다면? 어떻게 되는거지?
• $[5, 7, 4, 3, 6, 8, 1, 2]$를 해보자.
  • $[5, 4, 3, 6, 7, 1, 2, 8]$
  • $[4, 3, 5, 6, 1, 2, 7, 8]$
  • 두개 들고있다가 큰거 만나면 작은값 빼버려서 튀면 되는듯??

💻 풀이

#

• 코드 (C++):

void solve(){
    int N, K; cin >> N >> K;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    vector<int> ans;
    priority_queue<int, vector<int>, greater<int>> PQ;
    rep(i, 0, N){
        PQ.push(A[i]);
        if(PQ.size() > K){
            ans.push_back(PQ.top());
            PQ.pop();
        }
    }
    while(!PQ.empty()){
        ans.push_back(PQ.top());
        PQ.pop();
    }
    for(auto x: ans) cout << x << " ";
}