Hello!

백준 1377 버블소트

문제

버블소트가 몇 번 진행되는가?

풀이

버블 소트는 한번 진행될 때마다 각 숫자가 좌측으로 한칸씩 이동 가능하다.

따라서 좌측으로 이동하는 횟수가 버블 소트 진행 횟수이다.

image-20190828200704194

정렬 결과를 nlogn 정렬을 통해 알 수 있다는 것이 포인트.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<pair<int, int>> arr(n);
    for(int i=0; i<n; ++i) {
        int a; cin>>a;
        arr[i]={a, i};
    }
    sort(arr.begin(), arr.end());

    int ret=0;
    for(int i=0; i<n; ++i) {
        ret=max(ret, arr[i].second-i);
    }

    cout<<ret+1;
    return 0;
}

😄 유사문제

1517 버블소트

[jungin]
Written by@[jungin]
안녕하세요

GitHub