[1083] 소트

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

1083 - 소트

본문

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

입력

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

출력

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

제한

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

---

풀이

정렬하였을 때 최고의 정답은 이미 정해져 있다. 작은 수는 뒤에 오고, 큰 수는 앞으로 가야 한다. 최고의 정답은 가장 작은 수가 뒤에 오고, 가장 큰 수는 앞으로 가는 내림차순 배열일 것이다. 그리고 사전순으로 가장 뒤에 있으려면, 가장 큰 수가 가장 앞에 있는 것이 우선시되어야한다. 그럼 $S$번 이내에 가장 큰 수를 가장 앞에 오도록 할 수 있으면, 무조건 그렇게 하는 것이 옳다는 것이다. 그것을 기본적인 생각으로 코드로 구현해보자.

현재 내가 수를 옮길 수 있는 횟수가 $a$번 있다면, 우리는 가장 처음에 있는 수부터 $a+1$번째에 있는 수까지는 어떤 것이든 가장 앞에 오도록 할 수 있다. 그 이후에 있는 수들은 아무리 노력해도 가장 앞으로 오게 할 수는 없다. 정답을 찾기 위해서는 가장 앞에 있는 수는 가장 커야 하므로, 앞으로 올 수 있는 수들 중에서 가장 큰 수가 앞으로 오도록 해야 할 것이다. 즉 $b$번째 있는 수가 가장 큰 수고, 그 수가 제일 앞으로 올 수 있다면, 우리는 $b-1$번의 연산을 통해 일단 그 수를 제일 앞으로 옮겨야 한다는 의미이다. 간단한 예시를 통해 확인해보자.

3 5 1 2 4
move cnt : 2

위와 같은 예시가 있다고 가정한다면, 움직일 수 있는 연산의 횟수가 2번이므로 앞에서부터 3번째 숫자까지는 제일 앞에 올 수 있다. 즉 $3$, $5$, $1$은 가장 앞에 올 수 있는 숫자들이고, 그중에서 $5$가 가장 큰 수이므로, $5$를 제일 앞으로 옮기자. $3$과 $5$의 위치만 바꾸면 되므로 1번의 연산만 하면 옮길 수 있다.

5 3 1 2 4
move cnt : 1

첫번째 위치는 고정되었으니 2번째 위치에 어떤 수가 들어오면 되는지 생각해보자. 남은 연산은 1번이므로, 2번째 수부터 3번째 수까지 확인하면 된다. 그 수는 $3$과 $1$이고, 그중에서 숫자가 큰 것은 $3$이다. $3$은 이미 가장 앞에 존재하므로 넘어갈 수 있다.

이와 같은 방법으로 앞에서부터 재귀적으로 가능한 후보들 중 가장 큰 수와 그 위치를 찾고, 그 수를 옮겨주는 과정을 반복하면 답을 얻을 수 있다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 10 / 20

#include <stdio.h>

#define MAX_IDX 50

int arr[MAX_IDX];
int n;
int s;

#define min(a, b) (((a) > (b)) ? (b) : (a))

int argmin(int x, int y) {
    int retval = x;
    for (int i = x + 1; i < y; ++i) {
        if (arr[i] > arr[retval]) {
            retval = i;
        }
    }
    return retval;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }
    scanf("%d", &s);

    for (int i = 0; i < n; ++i) {
        if (s == 0) {
            break;
        }

        int target = argmin(i, min(i + s + 1, n));
        s -= (target - i);

        for (int j = target - 1; j >= i; --j) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }

    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}