[BOJ 1083] 소트

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

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

크기가 $N$인 배열을 최대 $S$번의 인접 원소 교환을 통해 사전 순으로 가장 뒷서는 상태로 만드는 문제다. 사전 순으로 가장 뒤에 온다는 것은 앞쪽 인덱스에 가능한 한 큰 숫자가 배치되어야 함을 의미한다. 이를 위해 매 단계에서 현재 위치에 올 수 있는 가장 큰 값을 찾아 앞으로 가져오는 그리디 알고리즘을 사용한다.

해결 과정은 다음과 같다:

1. 배열의 첫 번째 인덱스부터 마지막 인덱스까지 순차적으로 탐색한다.
2. 현재 인덱스 $i$에서 남은 교환 횟수 $S$ 내에 도달할 수 있는 범위 $[i, \min(i+S, N-1)]$를 설정한다.
3. 해당 범위 내에서 가장 큰 값의 위치 $target$을 찾는다.
4. 찾은 최댓값을 인접한 원소들끼리 자리를 바꾸며 현재 위치 $i$까지 끌어온다. 이때 사용한 교환 횟수는 $target - i$이며, 이를 전체 $S$에서 차감한다.
5. 남은 $S$가 $0$이 되거나 배열 끝까지 탐색을 마치면 과정을 종료한다.

배열의 크기 $N$이 $50$ 이하로 매우 작기 때문에, 매번 범위를 탐색하고 값을 이동시키는 방식은 다음과 같은 시간 복잡도를 가진다:

\[O(N^2)\]

$N=50$일 때 연산 횟수가 매우 적으므로 제한 시간 $2$초 내에 충분히 해결 가능하다. 매 순간 최선의 선택을 하는 것이 전체의 최적해를 보장한다.

소스코드

Github Link : Source Code

참고 알고리즘 : 그리디 알고리즘