[BOJ] 1377_버블 소트

버블 소트

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

1377번: 버블 소트

 

이 문제는 최종적으로 정렬이 되었을 때 몇 번째에서 정렬이 완료되었는지를 출력하는 것이 관건이다.

오름차순 정렬에서 버블소트는 가장 큰 수가 오른쪽으로 진행하게 된다.
이때, 한 번의 기회로 더 이상 횟수는 변하지 않는다.
하지만 작은 수는 왼쪽으로 이동을 수 없이 이동하게 될 것이다.
즉, 왼쪽으로 몇번 이동한지만 알 수 있다면 버블소트로 몇번만에 정렬이 되었는가를 알 수 있다.

 

이는 처음 입력되었을 때의 각 인덱스를 알고 있고, 이후 정렬된 인덱스의 차이를 보면 알 수 있다.
작은 값을 기준으로 생각했을 때 처음 입력되었던 위치에서 왼쪽으로 수 없이 이동 후 위치된 인덱스가 최종 위치이며, 정렬이 끝난 것이다.
만일 n번째에서 버블소트가 정렬이 되었다면 즉, 작은 값은 처음 입력된 위치보다 n-1번째 앞에 위치될 것이다.

 

• 정답 코드

    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define maxNum 500001
  
    int n;
    pair<int, int> a[maxNum];
  
    int main() {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i].first;
            a[i].second = i;
        }
        sort(a, a + n);
  
        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = max(answer, a[i].second - i);
        }
        cout << answer+1;
  
        return 0;
    }