[백준] 1377 버블소트 JAVA

1. 문제 설명

문제 설명

2. 접근 방식

해당 입력 값들로 오름차순 버블 정렬을 했을 때, 과연 외곽 Loop 몇 번만에 정렬이 완성될지 횟수를 출력하는 문제이다. 해당 문제를 버블 정렬를 직접 구현해서 푼다면, 데이터 크기가 500,000 이므로, 10^10이 되어 시간초과가 날 것이다. 따라서 다른 방법을 생각해야 한다.

값이 오른쪽에서 왼쪽으로 이동하는 것은 외곽 Loop 한 번당 최대 한 번 일어난다.

우리는 현재 조회 중인 원소와 오른쪽편 원소를 비교해서 왼쪽이 더 크면 자리를 바꾼다. 따라서 왼쪽에서 오른쪽 이동은 한번의 외곽 Loop 당 N번이 일어날 수 있지만, 오른쪽에서 왼쪽 이동은 한 번의 외곽 Loop 당 최대 1번이 일어난다. 이것을 이용해서 문제를 풀면 된다.
제일 많이 오른쪽에서 왼쪽으로 이동한 횟수만큼, 외곽 Loop가 돌았다는 것이고 이것을 출력하면 된다.

1. Node 클래스를 만들어서 정렬 전 Index와 value를 저장한다. 이것으로 배열을 만든다.
2. Arrays.sort()는 시간복잡도가 O(nlogn)이기 때문에 이를 이용하여 배열을 정렬한다.
3. 정렬 전 Index - 정렬 후 Index 로 왼쪽에서 오른쪽으로 이동한 횟수를 구한다.
4. 정렬이 완료된 이후에도 버블 정렬은 전부 정렬 되었는지 확인을 위해 외곽 Loop가 한 번 더 돌아야 한다 따라서 최대로 왼쪽에서 오른쪽 이동 횟수 +1 을 해줘야 한다.

3. 코드 분석

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

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

        Node [] nodes = new Node[N];

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

        Arrays.sort(nodes, Comparator.comparingInt(o -> o.value));

        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, nodes[i].idx - i);
        }

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

class Node {
    int idx;
    int value;

    public Node(int idx, int value) {
        this.idx = idx;
        this.value = value;
    }
}