[G3] 1377 : JAVA - 버블 소트

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

 

 

---

문제

버블 정렬 알고리즘을 빠삭히 알고 있어야 풀 수 있는 문제였다. 나는 못 풀었다. 핵심은 정렬이 완료된 시점을 찾아 내는 것! 

우선 나의 알고리즘 풀이 생각은 다음과 같았다.

 

 버블 정렬은 한 번 루프가 돌면 마지막 리스트 자리에는 정렬이 완료된 요소가 1개씩 추가된다. 이를 이용하여 정렬 전과 정렬 후를 비교해 정렬이 되지 않은 요소의 개수를 찾아내면 되지 않을까! 생각 했다. 정렬 전과 후를 비교하는 것은 매우 좋았지만 데이터를 직접적으로 비교하는 생각은 어리석었다. 왜냐하면 같은 요소가 여러 개 생기면 커버할 수가 없었다.

 

답의 핵심은 정렬 전과 후의 자리(인덱스)를 비교하는 것이였다. 버블 정렬은 한 번 루프를 돌 때 왼쪽으로 갈 수 있는 최대 위치는 1이다. 이를 이용해  정렬 후 가장 자리 차이가 많이 나는 인덱스가 답이 되는 것이다. 

 

답안 코드는 다음과 같다.

import org.w3c.dom.Node;

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 [] datas = new Data[N];
        for(int i=0; i< N; i++){
            // Data class 생성
            datas[i] = new Data(i, Integer.parseInt(br.readLine()));
        }

        // 정렬 (O(nlogn))
        Arrays.sort(datas);

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

    }
}

class Data implements Comparable<Data>{
    public int value;
    public int index;

    Data(){
        this.index = 0;
        this.value = 0;
    }
    Data(int value, int index){
        this.value = value;
        this.index = index;
    }

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

 

객체의 정렬

 자바에서는 객체의 정렬을 위해 java.util 라이브러리의 Arrays 클래스에서 sort함수를 지원한다. 아래 사진처럼 int형 리스트, byte형 리스트 등 다양한 자료형의 정렬을 지원하며, Object 리스트 또한 지원한다. 이때 Obejct 리스트의 정렬은 나머지 자료형의 리스트 정렬과는 다르게 compareTo 함수를 호출하여 정렬을 하게된다. 객체간의 정렬 조건은 제각각이기 때문에, 객체간의 우선 순위 여부를 정할 수 있도록 해당 함수를 오버라이딩하여 정렬 조건을 지정할 수 있다. 

Arrays.sort 함수의 종류

: compareTo()

compareTo 함수는 Comparable 인터페이스를 implements 함으로써 재정의할 수 있다. 아래 코드와 같이 정의할 수 있는데 양수를 리턴하면 this 객체가 더 큰것으로, 음수를 리턴하면 더 작은 것으로, 0을 리턴하면 같다는 의미이다. 이러한 재정의한 compareTo 함수를 통해 Arrays.sort 함수는 compareTo 함수를 호출하여 정렬을 진행한다.

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

 

 

생각해볼 점

1. 데이터의 비교가 힘들다면 인덱스 자리를 비교하는 것을 고려 해볼 것!
2.  반대 방향도 생각 해볼 것!
3.  전체 중 고르는 것이 아니라 가장 큰 수 하나만을 찾겠다는 생각을 해볼 것!