1377번 버블 소트(버블 정렬 원리) - ☆

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

<전략>

1. 버블소트를 몇단계에 걸쳐 진행하는가를 묻는 문제이다.

2. 버블 소트의 특징을 보면 가장 큰 수는 한 단계만에 맨 뒤로 가게 된다. 그에 반해 다른 수들은 모두 한칸씩만 앞으로 이동한다. 한칸씩 앞으로 이동한다는 말은 인덱스가 하나씩 줄어든다는 소리.

3. 즉, 정렬 전의 인덱스에서 정렬 후의 인덱스를 뺀 값이 가장 큰 수가 버블 소트의 단계를 결정짓는다.

4. 여기서 주의해야할 점은 차이의 절댓값이 가장 큰 수가 아니고, 작은 수는 한단계씩 거칠때마다 한칸씩 앞으로 오게 되므로 정렬 후의 인덱스가 정렬전의 인덱스보다 작을 수 밖에 없다. 결국, 정렬전 인덱스 - 정렬후 인덱스 의 값은 양수가 나올 수 밖에 없고, 이 양수 값중 가장 큰 값이 버블소트의 최종 단계가 된다.

Code