백준 11920번. 버블 정렬 (Java)

문제 링크 : https://www.acmicpc.net/problem/11920

버블 정렬의 중간 과정을 구하는 문제입니다.

N이 최대 10,000 이기 때문에 일반적인 버블 정렬을 돌리면 당연히 터집니다.

이 문제는 버블 정렬의 특징을 이해해야 합니다.

버블 정렬 한번 도는 과정이 총 N번 진행된다고 할 때, 정렬을 한번 수행할 때마다 가장 큰값은 맨 뒤로, 더 작은 값들은 한번씩 앞으로 이동합니다.

만약 K 번 수행한다면 가장 큰 수부터 K 번째 수까지 전부 뒤로 정렬된 상태입니다.

그러므로 우선순위큐를 이용하여 사이즈가 K만큼 유지되도록 만드는게 핵심입니다.

만약 우선순위큐에 K개의 숫자가 들어있는데 새로운 값이 들어온다고 가정합니다.

1. 기존의 K개의 숫자들보다 작은 값이 들어온다.

 => pq.poll() 하기 때문에 바로 출력됨

2. 기존의 K개의 숫자들과 비슷한 값이 들어온다.

 => pq.poll() 할 때 기존에 있던 값 중 가장 작은 값이 출력됩니다.

가장 작은 값이 출력되는 것은 똑같습니다.

하지만 핵심은 pq에는 항상 가장 큰 K개의 숫자들만 유지된다는 사실입니다.

만약 pq에 [4 5 6 7] 이렇게 들어있고 새로운 값으로 1, 3, 2 순으로 들어온다면 [1, 3, 2, 4, 5, 6, 7] 순으로 출력될겁니다.