[백준] 1377번 버블 소트 Java

문제 링크

https://www.acmicpc.net/problem/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이다.

출력

정답을 출력한다.

알고리즘: 정렬

풀이

문제의 소스를 그대로 옮기면 O(n제곱)으로 시간 초과가 난다.
버블 소트 자체에서 규칙을 찾아야 한다.
결론부터 말하면 리스트의 값 중 앞으로 가장 많이 이동한 횟수가 정답이다.
앞으로 이동하는 경우는 자신보다 큰 값이 스왑된 경우이고 i 횟수 한번당 앞으로 최대 한번 이동할 수 있다. 이 점을 이용해야 한다. 그러면 왜 가장 많이 이동한 횟수가 정답인지 의문이 들 수 있는데 다음 예를 보자
ex) 10 1 5 2 3 -> 1 2 3 5 10
1,5는 앞으로 총 한 번 이동했다.
2,3은 앞으로 총 두 번 이동했다.

앞으로 한 번 이동하고 그 이후에 이동하지 않았다는 것은 뒤에 더 이상 자신보다 큰 값이 존재하지 않는다는 의미이다. 그러면 위 같은 경우는 자연스럽게 가장 많이 이동한 횟수인 2번 이동하고 더 이상 어떠한 값도 앞으로 이동하지 않았다는 의미이므로 답은 앞으로 최대 이동한 횟수가 정답이 된다.

소스 코드

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

class NumInfo {
    int n,ind;
    NumInfo(int n, int ind) {
        this.n = n;
        this.ind = ind;
    }
}

public class Main {
    static int N;
    static int ans = -1;
    static ArrayList<NumInfo> list = new ArrayList<>();
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      for(int i=0; i<N; i++) {
          int n = Integer.parseInt(br.readLine());
          list.add(new NumInfo(n, i));
      }
      Collections.sort(list,(a,b) -> {
         return a.n - b.n; 
      });
      
      for(int i=0; i<N; i++) {
          int mc = list.get(i).ind - i;
          if(ans < mc) ans = mc;
      }
      System.out.println(ans + 1);
    }
}