[Java] 백준 1377 버블 소트

https://www.acmicpc.net/problem/1377

예제입력

5
10
1
5
2
3

예제출력

3

설명
이 문제는 주어진 숫자들을 몇회만에 swap 이 일어나지 않는지를 출력해내면 되는 문제이다.
swap 이 일어나지 않는다는 의미는 더 이상 정렬 할 구간이 없다는 의미로 정렬이 완료된 상태를 말한다.

버블 정렬로 구현을 하면 시간복잡도가 o(n^2) 인데 N의 최대가 50만 이므로 50*50은 이미 시간 초과가 되기 때문에 다른 방법으로 구현해보자.

입력 받은 배열의 인덱스와 정렬했을 때의 인덱스를 빼면 버블 정렬 했을 때 왼쪽으로 얼마나 이동했는지 알 수 있다.

여기서 제일 왼쪽으로 많이 이동한 값인 2가 이동횟수가 된다.

하지만 swap 할 것이 없는지 전체 배열을 한번 더 돌기 때문에 2 + 1인 3이 정답이 된다.

코드

class Data implements Comparable<Data> {
    int num;
    int index;

    public Data(int num, int index) {
        super();
        this.num = num;
        this.index = index;
    }

    @Override
    public int compareTo(Data o) {
        return this.num - o.num;
    }
}

    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());
            Data[] arr = new Data[n];

            for (int i = 0; i < n; i++) {
            // 값과 인덱스를 넣어준다.
                arr[i] = new Data(Integer.parseInt(br.readLine()), i);
            }
            Arrays.sort(arr);
            int max = 0;

            for (int i = 0; i < n; i++) {
            // i번째 인덱스에 저장되어 있는 인덱스 - 현재 i 가 max 보다 클 경우 저장
                if (max < arr[i].index - i) {
                    max = arr[i].index - i;
                }
            }
            // for 문 한번 더 도는 것을 감안하여 1을 더해준다.
            System.out.println(max + 1);
        }
    }