백준 1377

문제

 

문제 접근

정렬이 완료되었을 때 i를 출력하면 되는데, 직접 버블정렬을 구현해서 문제를 해결하면 $O(N^2)$이기 때문에 시간이 초과된다.

 

그래서 버블 정렬의 특성을 이용해서 문제를 풀어야한다.

버블 정렬은 정렬이 수행될 때마다 왼쪽으로 최대 한 칸씩 이동한다.

그래서 처음 위치에서 왼쪽으로 몇 칸 이동했는지에 따라서 몇 회 정렬되었는지를 확인할 수 있다.

 

예를 들어서 주어진 배열이 [10, 1, 5, 2, 3] 이렇다면,

정렬이 마무리되면 [1, 2, 3, 5, 10] 이다. (Java의 sort 메소드를 이용하면 N log N이다.)

3번인덱스인 2를 기준으로보면 정렬이 마무리 되었을 때 인덱스가 1로 변경된다.

그래서 왼쪽으로 2칸 이동했다는걸 알 수 있다.

 

그래서 정답은 각 원소의 인덱스 이동값을 비교해서 최댓값에 +1을 해주면된다.

+1은 정렬이 마무리되었는지 확인하는 턴이 있으므로 붙여준다.

 

코드 구현

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int[][] A = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            A[i][0] = i;
            A[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A, (a, b) -> {
            if(a[1] == b[1]) return a[0] - b[0]; // 값이 같을 땐 인덱스 순
            return a[1] - b[1];
        });

        int max = 0;
        for (int i = 0; i < N; i++) {
            if(A[i][0]-i > max) max = A[i][0]-i;
        }

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