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

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

문제 이름은 버블 정렬이지만 버블 정렬로 풀면 틀리는 문제입니다.

버블 정렬의 시간복잡도는 O(N^2)이고 N은 최대 500,000 이기 때문에 살짝만 계산해봐도 시간초과가 나온다는 사실을 알 수 있습니다.

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

버블정렬은 간단히 설명하자면 0번 인덱스부터 N-2번 인덱스까지 진행하면서 arr[i] 와 arr[i+1]을 비교하여 swap 하는 정렬입니다.

위와 같은 과정을 최대 N번 반복하면 정렬된 배열을 얻을 수 있습니다.

이때 문제에 나와있는 것처럼 flag를 써서 swap 여부를 체크하는 것처럼 약간의 최적화를 할 수 있습니다.

아무튼 다시 문제로 돌아오자면 핵심은 몇 번만에 정렬이 완료되었는가를 알아내는 것입니다.

그리고 정렬이 완료되었다는 것은 for문을 아무리 돌아도 각 변수의 이동이 없다는 것을 의미합니다.

이걸 또 다른말로 하면 변수의 이동이 존재한다면 정렬은 끝나지 않았다 가 됩니다.

서론이 길었는데 간단히 말하자면

정렬하기 전 인덱스와 정렬 후 인덱스를 비교해서 가장 많이 이동한 횟수를 출력한다

가 해법입니다.

그런데 무조건 많이 이동한 횟수는 아닙니다.

예를 들어 5 4 3 2 1 은 한바퀴 돌면 4 3 2 1 5가 되는데 가장 큰수는 마지막까지 이동하기 때문에 이동횟수가 가장 많습니다.

하지만 실제로는 한바퀴만 돌았죠

버블 정렬을 한 바퀴 돌때마다 큰 수들은 뒤로 끝까지 쭉쭉 밀립니다.

하지만 작은 수는 앞으로 한칸씩 땡겨집니다.

그렇기 때문에

정렬하기 전 인덱스 - 정렬 후 인덱스 > 0 인 후보들 중에서 고릅니다.

그렇다면 가장 작은 수를 기준으로 하면 되지 않느냐 할수도 있는데 그건 또 아닙니다.

예를 들어 3 1 4 2 5 를 정렬하면

가장 작은 수인 1은 앞으로 한칸만 간 후에 더이상 이동하지 않습니다.

하지만 완전한 정렬이 되기 위해서 2는 두칸을 이동하죠

그렇기 때문에 max 값을 구하는 겁니다.

가장 많이 이동한 값이 곧 마지막 까지 이동한 값이고 이것이 정렬을 하기 위해 얼만큼 반복했는지를 나타냅니다.

저는 현재 index와 value를 갖고 Comparable 인터페이스를 상속받아 value 를 기준으로 정렬되는 클래스를 만들었습니다.

그리고 입력받은 값을 우선순위큐에 담으면 value를 기준으로 정렬된 자료구조를 구할 수 있습니다.

그리고 기존에 갖고 있던 index값과 현재 idx값을 비교하여 최대값을 찾아 출력하였습니다.