[백준 1377] 버블 소트 (버블 정렬)

 

문제의 핵심은 버블정렬의 이중for문에서 안쪽 for문 전체를 돌 때 swap이 일어나지 않았을때의 횟수를 출력하는 것이다.

 

하지만 버블정렬을 이용하여 풀면 시간을 초과할 수 있어서 다른 아이디어를 사용해야합니다.

 

풀이

안쪽 루프는 1에서 n - j까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다. 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻이다. 즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 해결할 수 있다.

 

마지막에 정렬이 다 완료되어 swap이 일어나지 않는 반복문이 실행되는 것을 감안해 최댓값에 1을 더합니다.

 

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());
        mData[] A = new mData[N];
        for (int i = 0; i < N; i++) {
            A[i] = new mData(Integer.parseInt(br.readLine()), i);
        }
        Arrays.sort(A);
        int Max = 0;
        for (int i = 0; i < N; i++) {
            if (Max < A[i].index - i)
                Max = A[i].index - i;
        }
        System.out.println(Max + 1);
    }
}

class mData implements Comparable<mData> {
    int value;
    int index;

    public mData(int value, int index) {
        super();
        this.value = value;
        this.index = index;
    }


    @Override
    public int compareTo(mData o) {
        return this.value - o.value;
    }
}