[백준1377] 버블 정렬 소트

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

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

정답을 출력한다.

풀이

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

문제에서 제시한 소스코드
버블정렬에서 swap이 한 번도 일어나지 않은 루프를 알아내는 문제이다.

하지만 이대로 제출하면 시간복잡도에 막혀 시간초과가 뜬다.
시간복잡도를 줄여야한다.

 vector<pair<int,int>>arr(n+1);

먼저 pair 형으로 arr를 선언해준다.

 cin>>arr[i].first;
 arr[i].second = i;

입력을 받아준다.
i의 first에는 값을 second에는 i의 index를 순차적으로 넣어준다.

그렇게 되면 이렇게 저장이된다.
first 10 1 5 2 3
second 0 1 2 3 4

그 후 sort 함수로 수를 정렬한다. sort함수의 복잡도는 O(nlogn)이다.

sort로 2번째 index가 들어간 0,1,2,3,4는 정렬되지 않고
그대로 first가 정렬된 대로 딸려져 있다.

그 상태에서 정렬 후의 각 data에 index가 변화한 차이 중 제일 큰 값을 구하면 정답이된다.

data 1 2 3 5 10 <- arr[i].first
정렬전 1 3 4 2 0 <-arr[i].second
정렬후 0 1 2 3 4<-위와 동일
결과 1 2 2 -1 -4

마지막으로 swap이 일어나지 않는 반복문이 한번 더 실행되는 것을 감안해 최댓값에 1을 더한다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include<stdio.h>
using namespace std;



int main(void)
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    vector<pair<int,int>>arr(n+1);
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i].first;
        arr[i].second = i;
    };
    sort(arr.begin(), arr.end());
    int max = 0;
    for (int i = 1; i <= n; i++)
    {
        if (max < arr[i].second - i)
        {
            max = arr[i].second - i;
        }
        
    }
    cout << max + 1 << "\n";
   


}