[백준/BOJ] 1377 버블 소트 (c++)

[백준/BOJ] 1377 버블 소트 (c++)

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

 

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

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

 

---

최대 50만개의 배열이 주어지고 Bubble Sort를 수행했을때 몇번째 round에 정렬이 완료되는지를 알아내야 합니다.

input size를 보면 O(N^2) 시간복잡도인 Bubble Sort로 시뮬레이션 해볼수는 없기에 Bubble Sort의 특성을 이용해서 해결해야 합니다.

 

Bubble Sort 과정에서는 두개의 연속적인 요소들을 비교해서 변경하기 때문에 오름차순 정렬이라면,

각 round에서 Inversion 중 작은 값은 한번의 round에 1칸만 좌측으로 이동할 수 있습니다.

 

그러므로 Inversion 중 작은 값이 가장 많이 이동한 횟수를 찾으면 몇번의 round에 정렬이 완료되었는지 알 수 있습니다.

배열의 값, index 를 저장하고 sort를 이용해 배열의 값으로 오름차순 정렬을 해주면(O(NlogN)) 순차적으로 확인하면서 index 차이를 통해 몇 칸이 이동되었는지 쉽게 알 수 있습니다.

 

문제에서는 i를 1부터 시작했기 때문에 정답은 i+1 해주었습니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N;
vector<pair<int, int>> a;
int solve() {
    int ans = -1;
    REP(i, 0, N) {
        ans = max(ans, a[i].second-i);
    }
    return ans+1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    int x;
    REP(i, 0, N) {
        cin >> x;
        a.push_back(make_pair(x, i));
    }
    sort(a.begin(), a.end());
    cout << solve();
    return 0;
}