[BOJ/1377] 버블 소트

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

- https://www.acmicpc.net/problem/1377

 

사용 알고리즘

- 정렬

 

풀이

- Bubble Sort를 1회 수행 시, 숫자가 앞으로 1칸 밖에 이동하지 못함

- 따라서 앞으로 가장 많이 이동한 칸의 수 + 1

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/1377.cpp

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
 
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int n; cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    int ans = -1;
    for (int i = 0; i < n; ++i) {
        if (ans < (a[i].second - i)) ans = a[i].second - i;
    }
    cout << ans + 1 << "\n";
    return 0;
}