[백준] 1377번_버블 소트(Java)

문제 풀이

백준의 1377번 문제입니다. 문제 출처

(1) 문제 파악

버블 정렬 알고리즘을 통해 배열의 값을 정렬할 때 swap한 횟수를 구하는 문제입니다.

(2) 문제 풀이 방법 생각하기

문제에 주어진 코드를 그대로 사용해서 값을 구하면 N의 최대 값이 500_000이기 때문에 시간 초과가 나옵니다. (버블 정렬의 시간 복잡도는 O(n^2)입니다!)

한 번의 큰 루프가 수행될 때 특정 값이 이동할 수 있는 최대 거리는 1입니다. 즉, 데이터 정렬 전의 인덱스와 정렬 후 인덱스를 비교하여 가장 많이 왼쪽으로 이동한 값을 찾으면 문제를 해결할 수 있습니다.

여기서는 swap이 일어나지 않는 마지막 i까지 루프를 돌기 때문에 최대값 + 1이 정답입니다.

(3) 시간 복잡도 확인

시간 제한은 2초 입니다. 즉, 대략 2억번 연산 안에 문제를 해결해야 합니다.

Arrays.sort()의 시간 복잡도는 O(nlogn) 이며, 인덱스 차이 비교를 위한 루프는 N번 수행됩니다.

(4) 구현

import java.io.*;
import java.util.*;

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());
        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 gap = Integer.MIN_VALUE;
        for(int i=0; i<N; i++) {
            int n = arr[i].idx - i;
            gap = Math.max(gap, n);
        }
        
        System.out.println(gap+1);
        br.close();
    }
    
    static class Data implements Comparable<Data> {
        int value;
        int idx;
        
        public Data(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }
        
        @Override
        public int compareTo(Data d) {
            return this.value - d.value;
        }
    }
}