백준 1377 - 버블 소트

문제

 

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

1377번: 버블 소트

 

 

풀이

 

버블 정렬의 과정이 총 몇 단계로 이루어지는지 구하는 문제이다. 버블 정렬이 진행되는 과정을 통해 문제를 해결할 수 있다.

문제에 10 1 5 2 3 이 주어졌는데

i = 1 일 때 버블 정렬의 진행 과정을 보면 1 10 5 2 3, 1 5 10 2 3, 1 5 2 10 3, 1 5 2 3 10 순서로 된다. 10이 맨 뒤로 가게 된다.

i = 2 일 때 진행 과정은 1 2 5 3 10, 1 2 3 5 10 순서로 되고 정렬이 끝나게 된다. 5가 맨 뒤로 가게 된다.

 

즉 앞에서 뒤로 제일 큰 숫자를 순서대로 보내고 있다. 이때 뒤에서 앞으로도 이동하는 숫자들이 있는데, i번째에서 이 숫자들은 앞으로 1칸만 이동하게 된다. 이 점을 이용해서 버블 정렬이 몇 단계로 진행되는지 알 수 있다. 

초기 배열인 10 1 5 2 3 과 정렬 후 배열인 1 2 3 5 10 에서 앞으로 이동하는 숫자들이 앞으로 몇 번 이동하는지 구하면 된다. 그 중에서 최대값이 버블 정렬의 총 단계가 된다.

 

 

코드

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n;
pair<int,int> a[500001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        int num;
        cin >> num;
        a[i] = {num, i};
    }
 
    sort(a + 1, a + n + 1);
    
    int result = 0;
    for (int i=1; i<=n; i++)
    {
        if (a[i].second - i > result) result = a[i].second - i;
    }
 
    cout << result + 1;
 
    return 0;
}