[백준]#1377 버블 소트

문제

영식이는 다음과 같은 버블 소트 프로그램을 C++로 작성했다.

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

위 소스에서 n은 배열의 크기이고, a는 수가 들어있는 배열이다. 수는 배열의 1번방부터 채운다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구하는 프로그램을 작성하시오.

입력

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

출력

정답을 출력한다.

예제 입력 1

5
10
1
5
2
3

예제 출력 1

3

풀이

이 문제는 버블 소트를 진행할 때 정렬된 순서와 다른 순서인 숫자의 개수를 구하는 문제로 우선순위큐를 이용해서 풀었다.

버블 소트는 매 단계마다 숫자가 앞으로 당겨지기 때문에 앞으로 많이 당겨진 수의 당겨진 횟수를 이용해서 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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());
        PriorityQueue<Pair> queue = new PriorityQueue<>();
        int max = Integer.MIN_VALUE;

        for(int i=0; i<N; i++) {
            queue.add(new Pair(Integer.parseInt(br.readLine()), i));
        }

        for(int i=0; i<N; i++) {
            int index = queue.poll().index;
            if(index>i) {
                if(max<index-i)
                    max=index-i;
            }
        }

        if(max==Integer.MIN_VALUE)
            System.out.println(1);
        else
            System.out.println(max+1);
    }

    static class Pair implements Comparable<Pair>{
        int num;
        int index;

        public Pair(int num, int index) {
            this.num = num;
            this.index = index;
        }

        @Override
        public int compareTo(Pair pair) {
            if(this.num==pair.num)
                return this.index > pair.index ? 1 : -1;
            else
                return this.num > pair.num ? 1 : -1;
        }
    }
}