[백준/C++]#1377 - 버블 소트

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector <pair<int,int>> a(n);
    for(int i=0; i<n; i++)    {		// 입력
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(),a.end());
    int ans =0;
    for(int i=0; i<n; i++)    {		
        if(ans < a[i].second - i)	// 인덱스 차이 비교
            ans = a[i].second - i;
    }
    cout << ans+1;
    return 0;
}

개념

pair CTL을 사용한다. 처음 입력 시 인덱스의 값을 저장해야하는데, 정렬 후에는 인덱스 값이 변한다.

따라서 이 값을 pair를 통해 저장한다.

---

풀이

 

제목은 버블 소트이지만 버블 소트를 사용하면 문제를 해결 할 수 없다.

이 문제는 버블 소트의 예시를 통해 주어진 사례를 해결해야한다.

 

이 문제의 답은 3인데, 이를 풀기 위해 버블 소트의 특징을 생각해야한다.

한번 버블 소트를 실행하면 가장 큰 값이 맨 오른쪽으로 이동한다.

그리고 오른쪽에 있는(이동해야하는) 값들은 왼쪽으로 1만큼만 움직인다.

 

버블 소트의 횟수를 측정하기 위해서는 오른쪽->왼쪽의 최댓값을 구하면 된다.

이는 (이전에 저장한 배열 인덱스값) - (정렬 후 배열 인덱스값) 을 해서 구할 수 있다.

문제의 답은 이 결과에 +1을 해서 구할 수 있다.

 

---

+a

버블 소트를 사용하는 문제인줄 알고, 문제에 주어진 코드를 복붙했다가 시간초과 가 발생했다.

버블 소트는 O(N^2)의 시간복잡도를 가진 정렬이므로, 이와 같이 잘 쓰이지 않는다.

 

pair 기능 없이도 해결할 수 있겠지만, 코드를 좀 더 가시적으로 사용할 수 있어 유익하다.