[Baekjoon] 버블 소트

👀 문제 설명

문제

영식이는 다음과 같은 버블 소트 프로그램을 C++로 작성했다.

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

위 소스에서 n은 배열의 크기이고, 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

 

✍🏻풀이

버블 소트는 한번 진행될 때, 각 숫자가 좌측으로 한 칸씩 이동이 가능하다는 원리를 사용해 푸는 문제이다.

예를 들어, 10 1 5 2 3이 입력되었을 때, 첫 번째 턴에는 10을 정렬하기 위해 1, 5, 2, 3이 한 칸씩 왼쪽으로 이동하고 1 5 2 3 10으로 정렬이 된다. 두번째 턴에는 5를 정렬하기 위해 2, 3이 왼쪽으로 한칸씩 이동해 1 2 3 5 10으로 정렬이 된다.

이 원리를 사용해 푸는 문제이다.

최종적으로 정렬을 하면, 1 2 3 5 10이 되고, 정렬 전의 인덱스와 정렬 후의 인덱스를 비교하여 몇 번만에 정렬이 되었는지 구할 수 있다. 각 인덱스의 차이 중, 가장 최댓값 + 1을 출력하면 된다.

 

[참고]

https://scarlettb.tistory.com/114

 

코드

//  버블 소트 (https://www.acmicpc.net/problem/1377)

#include <iostream>
#include <vector>
#include <algorithm>

#define setIO ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define MAX 500001

using namespace std;

int n;
vector<pair<int, int>> a;

void input() {
    cin >> n;

    a.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a.at(i).first;
        a.at(i).second = i;
    }
}

int main() {
    setIO;
    input();

    sort(a.begin(), a.end());

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        if (answer < a.at(i).second - i)
            answer = a.at(i).second - i;
    }

    cout << answer + 1 << "\n";

    return 0;
}