BOJ 1838 버블 정렬

이 문제에서는 두 개의 버블 정렬 코드가 주어진다.
첫 번째 코드는 그냥 일반적인 n*n버블 정렬코드라고 보면되고, 두 번째 코드는 첫 번재 코드에서 바깥 for문이 n번 다 돌기전에 정렬이 완료되었을 경우 불필요하게 n번 다 돌지않고 중단하는 코드이다.
이 문제는 이 두 번째 코드로 주어진 수열을 정렬할 때, 정렬이 완료될 때까지 바깥 for문이 몇 번 도는지 구하는 문제라고 보면된다.

(오름 차순 기준) 버블 정렬의 특성을 잘 생각해봐야 한다.
바깥 for문이 한 번 돌때마다 주어진 수열의 수들의 위치가 조금씩 정렬되어 가는데, 한 번 돌 때마다 제자리를 찾은 값을 제외한 값들 중 가장 큰 값이 자신의 자리를 찾는다(맨 뒤로 간다), 반면 가장 큰 값이 아닌 값들은 어떻게 될까? 이것이 중요하다.
가장 큰 값이 아닌 값들은 앞으로 한 칸씩밖에 못 움직인다. 바로 이것이 핵심이다.
바깥 for문이 한 번 돌 때 앞으로 한 칸씩 움직이므로 주어진 수열과 정렬된 수열을 비교해서 각 수가 앞으로 움직인 칸의 수 중 최대값을 구하면 된다.

그리고 이 문제에서는 해당없지만 만약 주어진 수열에 같은 수가 있다면 어떻게 할까?
버블 소트는 stable sort(참고로 merge sort도 stable sort)이기 때문에 즉 값이 같다면 원래 수열의 순서를 유지한다. 그렇기 때문에 예를 들어 3번째 1이면 정렬 후 3번째 1과 비교하면 되는 것이다.

그리고 구현을 하자면 sorting을 할 때, index를 넣어서 같이 sorting을 해주고, sorting한 index와 비교해주면 될 것이다.

음 이 문제를 풀기 전에는 Bubble Sort를 이해하고 있다고 생각했는데, 이 문제의 풀이를 알게되니 내가 여태 Bubble Sort를 제대로 이해하지 못했단 것을 깨달았다. 이 문제를 통해 Bubble Sort에 대해 조금이나마 더 알게되었고... 역시 이 문제도 좋은 문제다.

출처 : 백준님 강의, 풀이, 강의자료