[Day05 - 1377번] 버블 소트

버블 정렬의 swap이 발생하지 않은 루프가 언제인지 알아내는 문제이다. 이 문제의 N의 최대 범위는 500000이기 때문에 버블 정렬도 문제를 해결할 경우 시간을 초과할 수 있다.(실제로 처음 문제를 풀었을 때 내가 그랬다;;;)

여기서 생각해봐야할 점은 안쪽 루프는 1 ~ n-i까지 swap을 수행한다는 것이다. 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리는 1이므로, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 된다는 것이다.

 

슈도코드를 작성하면 다음과 같다.

N(데이터 개수), A(데이터 배열 -> 클래스를 데이터로 담는 배열)

for (N만큼 반복) {

   A 배열 저장

)

A 배열 정렬

for (N만큼 반복) {

   A[i]의 정렬 전  index - 정렬 후 index 계산의 최댓값을 찾아 저장

}

최댓값+1을 정답으로 출력 -> swap이 일어나지 않는 마지막 반복문 횟수도 포함해야 하기 때문에

 

별도 클래스 선언

mData(데이터 표현) {

   index, value를 가지며

   value 기준 오름차순 정렬 함수 Comparable 구현

}

 

실제 구현 코드는 다음과 같다.

<hide/>
import java.io.*;
import java.util.*;

public class P_1377 {
   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) {  //A[i].index: 정렬 전 index, i:정렬 후 index
            max = A[i].index - i;
         }
      }
      System.out.println(max+1);  //swap이 일어나지 않은 마지막 반복문도 포함
   }
   
   static 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;
      }
   }
}

 

이때 JAVA 문법 하나 짚고 가자면,

1) extends vs implements

extends는 일반 클래스, abstract 클래스를 상속시키는 것으로, "A extends B = A는 B를 상속해 +a가 된다" 와 같다. 따라서 A는 B의 모든 것을 사용할 필요는 없다. 하지만 implements는 interface를 상속시키며 B에 있는 모든 것을 사용해야 한다.

 

2) Comparable<T> 인터페이스

Comparable 인터페이스는 객체를 정렬하는데 사용되는 메서드인 compareTo() 메서드를 정의하고 있다. 자바에서 같은 타입의 인스턴스를 서로 비교해야만 하는 클래스들은 모두 Comparable 인터페이스를 구현한다. 따라서 Boolean을 제욍한 Wrapper 클래스나 String, Time, Data와 같은 클래스의 인스턴스는 모두 정렬 가능하다. 이때 기본 정렬 순서는 작은 값에서 큰 값으로 정렬되는 오름차순이다.