문제 링크 : https://www.acmicpc.net/problem/1083
문제
크기가 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문제 풀이
N의 입력값이 적고 S의 범위도 널널하여 O(n^2)으로도 충분히 가능하다는 것을 우선 생각하게 되었다. 또한, 문제 이름과 같이 '특별한 조건'으로 정렬을 해나가야 한다. 문제 조건이 사전 순으로 가장 뒷서는 것을 출력하는 것이므로, S의 범위를 초과하지 않는 선에서 가장 큰 값을 찾아 왼쪽에 두게 되면 된다.
예시
6
3 5 9 1 2 4
4
[3 5 9 1 2 4]
1. 교환 횟수가 4회 이하일때, 고를 수 있는 가장 큰 값을 찾는다. 해당 값은 9이다.
[9 3 5 1 2 4]
2. 9가 제일 왼쪽에 가게 되고, 기존에 있던 9의 위치보다 왼쪽에 있던 것은 한칸 씩 오른쪽으로 옮겨지게 된다.
3. 교환 횟수는 2회(9가 이동한 칸수) 이다.
4. 1,2,3을 반복하되, 내림차순이 되거나, S가 0이하가 되거나,
더 이상 교환할 것이 없으면 종료한다.
시간 제한도 널널하여, 바로 O(n^2)로 코드를 짰고, 정답이었다.
#include <iostream>
#include <algorithm>
using namespace std;
int arr[51];
int n, s;
void input()
{
cin >> n;
for(int i=0; i<n; i++)
{
cin >> arr[i];
}
cin >> s;
}
void change(int cnt, int where)
{
int temp = arr[where]; // 가장 큰 수를 저장한다.
for(int i=where-1; i>=cnt; i--) // 놓을 위치의 숫자까지 오른쪽으로 한칸씩 옮긴다.
{
arr[i+1]=arr[i];
s--; // 이는 교환이 일어났다는 뜻이므로, 남은 교환 횟수를 빼준다.
}
arr[cnt]=temp; // 놓을 위치에 가장 큰 수를 넣는다.
}
void solve()
{
int top, where;
for(int i=0; (i<n && s>0); i++) // 교환 횟수가 있거나, 배열이 끝날 때까지 반복한다.
{
top = 0;
where = 0;
for(int j=i; (j<n && j<=s+i); j++) // 남은 교환수의 범위 안에 있어야 한다.
{
if(top < arr[j]) // 가장 큰 곳의 수와 위치를 갱신한다.
{
top = arr[j];
where = j;
}
}
change(i, where); // s 범위내에서 가장 큰 것을 찾아 왼쪽으로 배치한다.
// i는 놓을 위치, where는 범위 내에 존재하는 가장 큰 숫자의 위치 이다.
/*
// 교환 이후 배열의 상태
for(int i=0; i<n; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
cout << "left swap : " << s << '\n';
*/
}
// 최종 결과 출력
for(int i=0; i<n; i++)
{
cout << arr[i] << ' ';
}
}
int main()
{
input();
solve();
}
sorting 을 greedy 하게 하는 문제라서 신박했었던 문제였다.
냠냠