BOJ 1083 - 소트
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 128 MB |
문제
크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.
입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀게 된 계기
풀이 과정
문제의 조건은 일종의 버블 정렬을 하는 것인데, 버블 정렬로 n번째 위치에 있는 원소를 맨 앞으로 끌어오려면 n-1번의 스왑이 필요합니다. 1번의 스왑으로 인덱스 하나만큼 앞으로 당겨지니까요.
이제 사전 순 정렬을 생각해봅시다. 사전 순으로 배열을 비교할 때는 먼저 첫 원소를 비교하고, 첫 원소가 같으면 그 다음 원소를 비교하고, … 와 같이 비교를 하게 됩니다.
여기서 가장 중요한 점은, 어떤 배열을 다른 배열과 비교하여 첫 번째 원소가 사전 순으로 뒤에 오는 원소라면 뒤의 문자들을 비교할 필요 없이 그 배열 전체가 사전 순으로 다른 배열의 뒤에 온다는 것입니다. 예를 들면, 3 0 0 0 0이 2 9 9 9 9보다 뒤에 오는 원소인 것처럼요.
따라서, 가능한 한 가장 큰 원소를 배열의 맨 앞으로 보내는 작업을 어떻게든 해내야 할 것 같습니다. 맨 위에서 말했듯, S번의 스왑이 가능한 상태에서 어떤 원소를 배열의 맨 앞으로 가져오려면 그 원소의 인덱스 i는 \(0 <= i <= S\)이어야 합니다.
\(0 <= i <= S\) 구간의 원소 중 최댓값인 원소를 \(a\)라고 해 봅시다. 그럼 가능한 최종 배열의 첫 번째 원소가 바로 \(a\)가 되어야 합니다. \(a\)의 인덱스를 \(i_a\)라고 한다면, \(i_a\)번의 스왑을 통해 \(a\)를 배열의 첫 번째 원소로 만들어줄 수 있습니다.
이제 배열의 첫 번째 원소를 최댓값으로 정했습니다. 가능한 스왑 횟수는 \(S - i_a\)번이 남았고요. 역시 맨 위에서 말했듯, 첫 원소가 같으면 그 다음 원소를 비교해야 합니다. 따라서 바로 위의 과정을, \(1 <= i <= 1 + S - i_a\)번째 원소에 대해서 시행해주면 됩니다. 모든 원소를 순회했거나(정렬 완료) 가능한 스왑 횟수가 0이 될 때까지 위의 작업을 반복해주면 답을 얻을 수 있습니다.
예제 3번의 19 20 17 18 15 16 13 14 11 12, S = 5를 통해 예시를 들어 보겠습니다.
먼저 \(0 <= i <= 5\)번째 원소, 즉 19 20 17 18 15 16에서 최댓값 20을 찾아 줍니다. 그리고 20을 배열의 맨 처음으로 옮겨 줍니다. 이 과정에는 총 한 번의 스왑이 필요합니다. 결과적으로 20 19 17 18 15 16 13 14 11 12가 되었고, 남은 스왑 횟수는 4번입니다.
이제 \(1 <= i <= 1 + 4\)번째 원소, 즉 19 17 18 15 16에서 최댓값 19를 찾습니다. 19를 배열의 맨 처음으로 옮기는 데는 0번의 스왑이 필요하므로, 남은 스왑 횟수는 그대로 4번입니다.
마찬가지로 \(2 <= i <= 2 + 4\)번째 원소, 즉 17 18 15 16 13에서 최댓값 18을 찾습니다. 18을 배열의 맨 처음으로 옮기는 데는 1번의 스왑이 필요하므로, 남은 스왑 횟수는 3번이 되고 배열은 20 19 18 17 16 15 13 14 11 12가 됩니다.
이를 끝까지 반복해주면, 정답인 20 19 18 17 16 15 14 13 12 11를 얻을 수 있습니다.
구현
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i32 n, s;
array<i32, 50> arr;
i32 lo, max_idx, temp;
i32 main(void) {
fastio;
cin >> n;
for (i32 i = 0; i < n; i++) cin >> arr[i];
lo = 0;
max_idx = 0;
cin >> s;
while (s && lo < n) {
for (i32 i = lo; i < n && i - lo <= s; i++) {
if (arr[i] > arr[max_idx]) max_idx = i;
}
for (i32 i = max_idx; i > lo; i--) swap(arr[i], arr[i-1]);
s -= max_idx - lo;
max_idx = ++lo;
}
for (i32 i = 0; i < n; i++) cout << arr[i] << ' ';
}
\(N <= 50\)이므로 풀이를 정직하게 구현만 해 주면 간단히 통과할 수 있습니다.
마치며
그리디하게 접근할 수 있다는 것을 파악하면 어려운 문제는 아니었던 것 같습니다. 그리디 문제를 많이 안 풀어봐서 생소한 접근이긴 했지만, 그래도 금방 깨닫고 구현할 수 있어 다행이었습니다. 다른 마라톤 세트는 모조리 구현이었던 바람에 이 문제가 그나마 숨통을 틔워 줬던 기억이 납니다.