Do it! 알고리즘 코딩테스트 | 2. 정렬 - 버블 정렬 | 016 버블 정렬 프로그램 1

문제 정보 백준 1377번 버블 소트 https://www.acmicpc.net/problem/1377

 

문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

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;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

입력

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

출력

정답을 출력한다.

예제 입력 1 

5
10
1
5
2
3

예제 출력 1 

3

예제 입력 2 

5
1
3
5
7
9

예제 출력 2 

1

 

//정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    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()); //A배열 정렬 O(nlogn)시간 복잡도

    int Max = 0;
    for (int i = 0; i < N; i++) {
        if (Max < A[i].second - i) //정렬 전 index - 정렬 후 index 계산 값의 최대 값을 찾아 저장
            Max = A[i].second - i;
    }
    cout << Max + 1;
}

 

버블 정렬이 진행 되며 SWAP이 한 번도 일어나지 않은 루프를 찾는 문제이다. 문제 이해하는데 좀 오래 걸리긴 했는데 그냥 간단하다.