버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개의 서로 다른 정수가 A[0], A[1], ..., A[N-1]의 정수형 배열에 저장되어 있고, 이를 오름차순으로 정렬하기 위해 태국이는 다음과 같은 코드를 작성하였다.
for (i=0; i<N; i++) {
flag = 0;
for (j=0; j<N-1; j++) {
if (A[j] > A[j+1]) {
flag = 1;
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
하지만 주어진 배열 A에 따라 변수 i가 모든 loop를 반복하지 않아도 정렬이 완료되기도 한다. 따라서 도현이는 다음과 같이 코드를 개선하였다.
for (i=0; i<N; i++) {
flag = 0;
for (j=0; j<N-1; j++) {
if (A[j] > A[j+1]) {
flag = 1;
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
if (flag == 0) {
break;
}
}
도현이는 자신이 태국이보다 우월하다는 것을 증명하기 위해, 개선된 코드를 이용하여 주어진 배열 A를 정렬해 보려고 한다. 만일 정렬이 완료되었을 때(즉 for문을 빠져나왔을 때)의 i값이 작으면 작을수록 도현이의 코드가 더 빠른 것이 된다. 태국이를 이기고 싶은 도현이를 도와서, 배열 A에 저장된 수가 주어지면 정렬이 완료되었을 때 변수 i에 저장되어 있는 값을 구하는 프로그램을 작성하시오.
첫째 줄에는 정수 N(1≤N≤500,000)이 주어진다. 다음 줄에 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 순서대로 주어진다. 주어지는 정수는 절댓값이 2,147,483,647을 넘지 않는다.
첫째 줄에 정렬이 완료되었을 때 변수 i에 저장되어 있는 값을 출력한다.
5
30 10 44 27 49
2
이 문제는 버블 소트를 진행할 때 정렬된 순서와 다른 순서인 숫자의 개수를 구하는 문제로 우선순위큐를 이용해서 풀었다.
버블 소트는 매 단계마다 숫자가 앞으로 당겨지기 때문에 앞으로 많이 당겨진 수의 당겨진 횟수를 이용해서 풀었다.
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;
String[] input = br.readLine().split(" ");
for(int i=0; i<N; i++) {
queue.add(new Pair(Long.parseLong(input[i]), 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(0);
else
System.out.println(max);
}
static class Pair implements Comparable<Pair>{
long num;
int index;
public Pair(long 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;
}
}
}