버블 소트

https://www.acmicpc.net/problem/1337

---

풀이

버블 정렬은 위 그림처럼 앞뒤 원소를 비교해가며 마지막 원소부터 정렬한다.
하지만 문제에서 버블 정렬을 사용하면 시간 초과가 발생하게 된다.
문제에서 제시된 코드를 보면 마지막 원소를 선택하는 것을 1웨이브라고 했을 때 몇 번째 웨이브 때 정렬이 되는가를 묻고있다.
이를 위해서는 가장 이동 횟수가 많은 원소를 찾으면 된다.
왜냐하면 한 웨이브당 한 번의 움직임을 갖기 때문에 이동이 가장 많은 원소가 버블 정렬의 웨이브 횟수와 같다.

입력값과 그 순서를 쌍으로 받는 리스트(l)를 만든다.
그 리스트를 오름차순으로 정렬하고 0부터 리스트의 크기(N)만큼 인덱스를 반복하며 리스트의 저장된 순서에 인덱스를 빼며 그 차가 가장 큰 값을 결과값으로 저장한다.
정렬되기 전 순서값과 정렬된 후의 순서값을 빼면 움직임의 크기가 나오기 때문이다.
마지막으로 결과값에 1을 더하여 출력하는데 문제에서 반복을 1부터 N+1까지 하기 때문이다.