[1377번] 버블 소트

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 버블 소트

이 문제는 버블 소트가 어떻게 동작하는지만 이해한다면 쉽게 풀 수 있는 문제이다.

버블 소트가 한번 이루어지면 오른쪽으로는 몇번 움직일 지 모르지만, 왼쪽으로는 어떤 수든 딱 한번만 움직인다.

따라서 처음 입력 받을 때 index를 같이 입력받아 둔 후, 정렬을 시키고 나서 

각 수의 현재 index - 이전의 index가 가장 큰 값을 찾는다면 그것이 정답이 된다.

즉, 버블 소트 한번당 왼쪽으로 어떤 수가 최대 한번 움직일 것이니, 

버블 소트 n번이 일어나면 어떤 수는 최대 왼쪽으로 n번 움직일 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
#define swap(a,b){int t = a ; a = b; b = t ;}
 
using namespace std;
 
typedef pair<int, int> pii;
 
vector<pii> vc;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
        vc.push_back({ val, i });
    }
 
    sort(vc.begin(), vc.end());
 
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, vc[i].second - i);
 
    cout << ans + 1;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>