백준 1377번 버블 소트 (Java)

문제

백준 1377번 버블 소트 / 골드2
버블 소트 알고리즘을 다음과 같이 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이다.

풀이

위 소스코드는 전형적인 버블 소트의 최적화 버전이다. 사이클 중간에 정렬이 완료되었는지 검사를 통해 추가적인 사이클 중단하고 사이클이 몇 번 동작했는지 출력하는 소스코드이다.

버블 소트의 동작 원리를 잘 이해하는지, 이를 어떻게 응용해서 해결할 수 있는지 고민해 보는 문제이다. 하지만, 버블 소트의 원리를 이해한다고 해도 버블 소트로 문제를 해결하려면 O(N²)로 시간 초과가 발생한다.

그렇기에 정렬은 다른 정렬을 사용해 주고, Input 객체를 만들어 정렬 전 숫자의 index 값을 저장해주었다. 오름차순 버블 정렬은 한 사이클에 검사하는 input 중 가장 큰 수를 맨 뒤로 보내고, 정렬 위치보다 뒤에 있는 작은 수들은 한 칸씩 앞으로 당겨준다. 그렇기에 앞쪽 칸으로 이동하는 수가 최대일 때, 이 수는 최대 정렬 횟수를 나타내고 다른 수는 정렬이 완료되는 현상이 발생한다.

이를 구하기 위해 단순하게 모든 input의 기존 index와 정렬 이후의 index의 차이의 최댓값을 구해주었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Input[] input = new Input[N];
        for (int i = 0; i < N; i++) {
            input[i] = new Input(i, Integer.parseInt(br.readLine()));
        }

        Arrays.sort(input);

        int result = 0;
        for (int i = 0; i < N; i++) {
            if(result < input[i].index - i ) {
                result = input[i].index - i;
            }
        }

        System.out.println(result + 1);
    }
}

class Input implements Comparable<Input> {
    int index;
    int value;

    Input(int index, int value) {
        this.index = index;
        this.value = value;
    }

    @Override
    public int compareTo(Input o) {
        return this.value - o.value;
    }
}