1377 버블 정렬

지름길

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

설명

– 각 버블 정렬에 대해 마지막 값이 결정됩니다.

– 각 작업에 대해 왼쪽으로 한 칸 이동

– 이 변경을 이용하면 왼쪽으로 이동한 값 중 최대값이 발생한 만큼 최대값에 +1을 더하면 변경이 잘못되었을 때 그 값을 얻을 수 있다.

암호

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

public class BJ_1377_버블소트 {
    public static void main(String() args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Num() arr = new Num(N);
        for(int i = 0; i < N; i++){
            int num = Integer.parseInt(br.readLine());
            arr(i) = new Num(num, i);
        }
        Arrays.sort(arr);
        int max = 0;
        for(int i = 0; i<N; i++){
            Num num = arr(i);
            max = Math.max(num.index - i, max);
        }
        int res = max + 1;
        System.out.println(res);
    }
    public static class Num implements Comparable<Num>{
        int num;
        int index;
        public Num(int num, int index){
            this.num = num;
            this.index = index;
        }
        public int compareTo(Num o){
            return this.num - o.num;
        }
    }
}