[백준 1377번] 버블 소트 (C++)

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

1377번: 버블 소트

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
vector<pii>v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    v.resize(N);
    for(int i=0; i<N; i++)
    {
        cin >> v[i].first;
        v[i].second = i; //인덱스 저장
    }
    sort(v.begin(), v.end());
    int result = 0;
    for(int i=0; i<N; i++)
    {
        result = max(result, v[i].second-i); //인덱스 차이가 정렬 횟수
    }
    cout << result+1; //마지막 체크 + 1
    return 0;
}

코드가 주어져 있지만 해당 코드를 그대로 쓰면 시간초과가 나는 문제이다.

코드가 요구하는 것이 버블 정렬을 할 때 필요한 총 횟수라는 것만 알면 된다.

 

한번 버블 정렬을 실행할 떄마다 가장 큰 값이 맨 오른쪽으로 가고, 이때 오른쪽에 있던 값들은 왼쪽으로 이동한다.

이를 이용하여 오른쪽에 있던 값중에서 왼쪽으로 제일 많이 이동한 값을 찾으면 면된다.

(오른쪽 -> 왼쪽 한번의 이동이 한번의 버블 정렬을 나타내기 때문)

 

이를 위해서 처음 값들에 대한 인덱스를 저장하고, 이후 정렬을 한 후 인덱스도 확인하여 인덱스의 갭이 제일 큰 값을 출력해주면 된다.

갭이 음수인 경우는 왼쪽->오른쪽으로 이동함에 따라 생긴 경우이므로 고려해줄 필요가 없다.

 

이때 예제로 주어진 코드에서는 정렬을 다하고 마지막 체크를 한번 더 해주므로 (FASLE 확인) 인덱스의 갭에 + 1을 해주고 출력을 해주어야 한다.