[Java] 1377 버블 소트

문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

 

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력

정답을 출력한다.

 

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(bufferedReader.readLine());
        mData[] arr = new mData[num];
        
        for(int i=0; i<num; i++){
            arr[i] = new mData(Integer.parseInt(bufferedReader.readLine()), i);
        }
        Arrays.sort(arr);
        
        int max = 0;
        for(int i=0; i<num; i++){
            if(max < arr[i].index - i)
                max = arr[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;
    }
}

▶ int num = Integer.parseInt(bufferedReader.readLine()) : 사용자로부터 데이터 개수를 입력받아 num 변수에 저장함

▶ mData[] arr = new mData[num] : 입력받은 수를 담을 배열 arr를 num 크기만큼 선언함

▶ for(int i=0; i<num; i++){ arr[i] = new mData(Integer.parseInt(bufferedReader.readLine()), i) } : arr 배열의 값을 사용자로부터 입력 받음

▶ Arrays.sort(arr) : array 배열을 오름차순으로 정렬함

 

int max = 0;

for(int i=0; i<num; i++){
    if(max < arr[i].index - i)
        max = arr[i].index - i;
}
System.out.println(max+1);

▶ 정렬 전 index - 정렬 후 index를 계산해 최대값을 구한 후 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 최댓값에 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;
    }
}

▶ mData 클래스를 별도로 선언해줌

▶ 2차원 배열로 구현하면 Arrays.sort를 쓰지 못하게 되어 복잡해 지고 배열을 두 개 만들면 원래 인덱스의 값을 구별할 수 없어 Comparable 인터페이스를 구현

▶ mData 클래스는 부모 클래스로부터 상속받은 필드나 메소드를 자식 클래스에서 참조하는 데 사용하는 참조 변수 super()를 선언함

Comparable
▶ Comparable 인터페이스에는 compareTo(T o) 메소드 하나가 선언되어 있음
▶ Comparable을 사용하고자 한다면 compareTo 메소드를 재정의(Override) 해줘야