문제의 코드는 작은 수를 오른쪽(큰 수)으로 옮겨가면서 정렬이 다 되었을 때 종료한다. 반복문에서 i의 증가 횟수는 이동한 수의 개수와 같은 데,
한 원소가 자신의 위치로 이동하는 최소 거리들 중 최대값과 같다.
다시 말하면, 가장 멀리 (오른쪽으로) 이동하는 원소의 거리이다.
Lower/Upper bound 를 사용하는 이유는 [ 3, 1, 7, 5, 3 ] 의 경우 3이 이동해야 하는 최소거리는 현재 3의 위치마다 다르기 때문이다.
3 1 7 5 3
1 3 3 5 7
첫번째 3의 경우에는 오른쪽으로 1만 이동하면 되고, 마지막 3은 왼쪽으로 2만 이동하면 된다. 첫번째 3의 입장에서는 lower_bound 를, 마지막 3의 입장에서는 upper_bound 를 사용하면 그 거리가 나온다.
댓글 없음:
댓글 쓰기