두 원소 바꾸기

순열의 인버전 수를 생각하자. 연산에서 실제로 자리를 바꾸는 두 원소의 값을 $x<y$라고 하자. $x$와 $y$는 고른 구간에서 가장 작은 원소와 두 번째로 작은 원소이므로, 두 위치 사이에 있는 모든 원소는 $y$보다 크다. 따라서 이 중간 원소들과 $x,y$가 만드는 인버전의 총수는 교환 전후에 변하지 않고, $x$와 $y$ 사이의 인버전 여부만 바뀐다. 그러므로 한 번의 연산은 전체 인버전 수를 정확히 $1$만큼 증가시키거나 감소시킨다. 정렬하려면 모든 인버전을 없애야 하므로 필요한 연산 횟수는 처음 인버전 수 이상이다.

길이 $2$인 구간 $[i,i+1]$을 고르면 그 두 원소가 바로 가장 작은 원소와 두 번째로 작은 원소이므로 두 원소를 단순히 교환하는 연산이 된다. 따라서 인접한 역전쌍을 하나씩 교환하는 버블 정렬을 그대로 사용할 수 있다. 각 교환은 인버전을 정확히 하나 줄이고, 모든 인버전이 사라지면 정렬된다.

따라서 버블 정렬의 교환 횟수가 최소 연산 횟수이다. 시간 복잡도는 $O(N^2)$이고, 출력되는 연산 수도 최대 $N(N-1)/2$개이다. Solution written by GPT5.6