[백준] 1377 버블 소트

문제 링크

http://icpc.me/1377

1377번: 버블 소트

풀이

개인적으로 알고 나면 쉽지만 아이디어가 많이 어려운 문제인 것 같다.

문제를 잘 관찰을 해본다면 출력을 하는 수는 정렬이 끝난 다음 시점의 i값이다.

편의상 인덱스가 작은 방향을 왼쪽, 큰 방향을 오른쪽이라 하겠다.

정렬이 모두 끝난 시점을 알기 위해서는 왼쪽으로 밀려난 수 중 가장 많이 밀려난 수가 몇 번 왼쪽으로 밀려났는지를 알면 된다. 

그 이유는 왼쪽으로 가야 하는 어떤 수는 한번 바깥 루프를 돌 때마다 한 칸밖에 움직일 수 없다.

그렇기 어떤 수가 왼쪽으로 x칸 가기 위해선 i가 최소한 x가 돼야 한다. 

그렇기 때문에 수를 정렬하고 기존의 인덱스 값과의 차가 가장 큰 것을 출력하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

pair<int, int> arr[500005];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int inp; cin >> inp;
        arr[i] = {inp, i};
    }
    sort(arr, arr + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, arr[i].second - i);
    }
    cout << ans + 1;
}