1. 문제

📌 문제 보러 가기!

2. 접근법

버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지를 알아내는 문제입니다.
즉, 이미 모든 데이터가 정렬되어 swap이 일어나지않은 때를 의미합니다.
이중 for문 중 안쪽 for문이 몇 번 수행됐는지 구하는 아이디어가 필요합니다.

안쪽 루프는 1에서 n - j까지, 즉 왼쪽에서 오른쪽으로 이동하며 swap을 수행합니다.
이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이루동할 수 있는 최대 거리가 1이라는 뜻입니다.
즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 문제를 해결할 수 있습니다.
swap이 일어나지 않는 루프 한 번을 더하면 정답입니다.
왜 오른쪽은 안 되는가? --> 한 루프에 오른쪽으로는 여러번 이동할 수 있기 때문입니다.

3. 코드

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

public class BaekJoon1377 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Node[] arr = new Node[N];

        for (int i = 0; i < N; i++) {
            arr[i] = new Node(Integer.parseInt(br.readLine()), i);
        }

        Arrays.sort(arr);

        int m = 0;

        for (int i = 0; i < N; i++) {
            int t = arr[i].index - i;
            if (t > m) {
                m = t;
            }
        }
        System.out.println(m + 1);
    }

    static class Node implements Comparable<Node> {
        int num;
        int index;

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

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