소트
알고리즘 구분 : 그리디, 정렬
문제
크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.
입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
7
10 20 30 40 50 60 70
1
예제 출력 1
20 10 30 40 50 60 70
예제 입력 2
5
3 5 1 2 4
2
예제 출력 2
5 3 2 1 4
예제 입력 3
10
19 20 17 18 15 16 13 14 11 12
5
예제 출력 3
20 19 18 17 16 15 14 13 12 11
문제 풀이
문제에 유심히 봐야할 포인트는 크게 3개다.
1. 정렬 시, 연속된 두 개의 원소만을 교환할 수 있다.
2. 교환은 최대 S번 할 수 있다.
3. 정렬한 결과를 내림차순으로 출력해야 한다.
이렇게 3가지이다.
아래의 틀린 접근을 한 번 경험한 뒤에, 테스트 케이스를 직접 하나 만들어서 생각해 보았다.
Input
7
10 20 30 70 40 50 60
3
정답 Output
70 10 20 30 40 50 60틀린 Output
20 30 70 10 40 50 60
내 처음 접근 방식은 위의 틀린 Output 값을 가지게 된다. 즉, 연속으로 연결되어 있는 두 수만 교환가능하지만, 교환가능한 거리 안에 더 큰 수가 있을 경우, 해당 수를 기준으로 교환을 진행해야 하는데, 그 부분을 틀린 코드에서는 진행이 불가능한 것이였다. 그렇기에, 교환 가능 횟수인 s번의 범위 안에서 가장 큰수를 찾아 해당 수를 기준으로 교환을 진행할 수 있도록 해야 한다.
즉, 현재 인덱스의 수를 가장 큰 수라는 가정을 잡은 뒤, 교환 가능한 거리까지의 반복문을 통해 더 큰 수가 존재한다면, 해당 수를 가장 큰 수로 갱신하는 과정을 거친 뒤, 해당 큰 수의 인덱스부터 현재 인덱스까지의 교환을 swap함수를 통해 진행할 수 있도록 구현하면 된다.
위의 진행 방식은 버블 정렬(Bubble Sort)알고리즘을 직접적으로 구현하는 문제다.
버블 정렬 : 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘으로, 2개의 인접한 값을 비교하여 크기가 순서대로 되도록 교환하는 과정을 진행하는 정렬을 의미한다.
버블 정렬에서는 전체를 한번 순회할 때마다 정렬이 완료된 데이터가 하나씩 늘어나는 정렬 방식이다.
틀린 접근 방식
문제를 딱 읽었을 때, 연속된 두 개의 원소만 교환할 수 있고, 내림차순으로 정렬이기에, 맨 앞의 인덱스부터 차례차례 그리디하게 교환가능 여부를 체크하면서 맨 뒤까지 정렬을 진행하면 되겠다라고 판단하여 구현했다. 해당 방식으로 예제 역시 다 정답을 받았으나, 제출 결과 WA를 받았다.
틀린 소스 코드#include <bits/stdc++.h> using namespace std; int n, s; vector<int> v; void solve(); int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 0; i < n; i++) { int input; cin >> input; v.push_back(input); } cin >> s; solve(); return 0; } void solve() { int front, back; vector<int> result; if(s == 0) { for(int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; return; } front = v[0]; for(int i = 1; i < n; i++) { back = v[i]; if(s == 0) { result.push_back(front); for(int j = i; j < n; j++) { result.push_back(v[j]); } break; } if(front > back) { result.push_back(front); front = back; if(i == n - 1) { result.push_back(front); } } else if(front < back) { result.push_back(back); s--; if(i == n - 1) { result.push_back(front); } } } for(int i = 0; i < result.size(); i++) { cout << result[i] << " "; } cout << endl; }
소스 코드
#include <bits/stdc++.h>
using namespace std;
int n, s;
vector<int> v;
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++) {
int input;
cin >> input;
v.push_back(input);
}
cin >> s;
solve();
return 0;
}
void solve() {
int maxNum, maxIdx;
for(int i = 0; i < n; i++) {
maxNum = v[i];
maxIdx = i;
for(int j = i + 1; j < n; j++) {
if(s - (j - i) >= 0) {
if(maxNum < v[j]) {
maxNum = v[j];
maxIdx = j;
}
}
}
for(int j = maxIdx; j > i; j--) {
swap(v[j], v[j - 1]);
}
s -= (maxIdx - i);
if(s <= 0) {
break;
}
}
for(int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}- 문제 출처 : https://www.acmicpc.net/problem/1083
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
