백준 1377 버블 소트 | C++

 

이번 포스팅은 백준 1477번 버블 소트입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/1377

1377번: 버블 소트

 

 

기본 알고리즘

버블 소트

 

풀이

 

문제에 주어진 코드를 사용하면 시간 초과 판정이 나므로 문제에서 요구하는 출력값이 무엇인지 파악해야 한다.

 

출력 값 i는 버블 정렬을 몇 번째 수행에서 버블 정렬이 완성되는지 출력하는 값이다.

 

i=1 10 1 5 2 3 1 10 5 2 3 1 5 10 2 3 1 5 2 10 3 1 5 2 3 10 i=2 1 5 2 3 10 1 2 5 3 10 1 2 3 5 10 i=3 1 2 3 5 10

 

주어진 버블 정렬 코드에 의해

배열에서 연속된 인덱스를 가진 숫자 2개 중

그 값이 작아 좌측으로 자리를 이동하는 경우는 i for문 내부에서 1번만 가능하다.

(좌측으로 밀려나는 일은 없기 때문)

 

즉,  배열의 값이 몇 번 인덱스로 이동했는지 구하면 버블 정렬 횟수를 알아낼 수 있다.

 

정렬 전과 정렬 후의 인덱스를 비교하여 좌측으로 이동한 값 중 그 차가 가장 큰 값이 출력 값이 된다.

 

정렬 전

[ 0    1    2    3    4 ]

10    1    5    2    3

 

정렬 후

[1    3    4    2    0 ]

 1    2    3    5    10

 

인덱스의 차를 구하여 그 값이 양수이면 좌측으로 이동했음을 알 수 있다.

 

1    3    4    2    0

0    1    2    3    4

                    

1    2    2    -1    -4

 

인덱스의 차 중 가장 큰 값+1이 원하는 출력 값이다.

 

 

 

전체 코드

//백준1377 버블소트                                                            
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first;
        v[i].second = i;
    }
 
    sort(v.begin(), v.end());
 
    int ans = -1;
    for (int i = 0; i < n; i++) {
        if (ans < v[i].second-i) {
            ans = v[i].second - i;
        }
    }
 
    cout << ans + 1;
}