백준 1083. 소트

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

1083번: 소트

 

처음에 보면 뭔가 버블소트와 관련이 있어 보이지만, 자리를 바꿀수 있는 횟수가 제한되 있고, 최대한 사전순 가장 마지막인 배열을 출력해야 하기 때문에 별로 관련이 없다.

 

사전순 가장 뒷선 배열이 되려면 최대한 큰 수가 앞으로 와야한다.

S가 남은 swap 가능 횟수라고 할때 

a[i+1] 부터 a[i+S] 까지 중 가장 큰 수를 swap 하면서 i 자리로 오게 한다.

물론 a[i] 보다 큰 수가 없다면 swap 하지 않는다.