[C++] 1083번: 소트

링크

https://www.acmicpc.net/problem/1083

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

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	
	int count = 0;
	int n;
	cin >> n;
	vector<int> sort(n);

	for (int i = 0; i < n; i++)	
		cin >> sort[i];

	int s = 0;
	cin >> s;

	for (int i = 0; i < n; i++)
	{
		int maxNum = sort[i];
		int	maxIndex = i;
		for (int j = i; j < n; j++)
		{
			if (sort[j] > maxNum && j - i <= s)
			{
				maxIndex = j;
				maxNum = sort[j];
			}
		}

		if (maxIndex != i)
		{
			sort.erase(sort.begin() + maxIndex);
			sort.insert(sort.begin() + i, maxNum);
			s -= (maxIndex - i);
		}

		if (s == 0) break;
	}


	for (auto temp : sort)
		cout << temp << " ";
}

풀이

• 그리디 알고리즘을 이용해서 풀었다.
• 처음에는 버블정렬처럼 s 만큼의 횟수로 n과 n+1의 위치를 바꾸는 문제인 줄 알았는데
  그런 의미의 문제가 아니었다.
  
  
• s번 숫자를 움직일 수 있다는 뜻이였고
  
  

10
19 20 17 18 15 16 13 14 11 12
5

 

이런 입력이 들어온다면 5칸으로 맨 앞까지 움직일 수 있는 수 중 가장 큰 값을 찾아서 옮기면 된다.

			if (sort[j] > maxNum && j - i <= s)
			{
				maxIndex = j;
				maxNum = sort[j];
			}

현재 인덱스의 숫자가 지금까지 저장한 최대 숫자보다 크다면 최대 숫자에 현재 숫자를 넣는다.

또한 j - i 는 현재 위치( j )에서 옮기려 하는 위치( i )를 뺀 값으로 숫자가 움직여야 할 칸을 나타낸 수다.
이것이 s보다 작거나 같으면 움직일 수 있게 하여 움직일 수 있는 횟수를 넘지 않도록 한다.

 

10
19 20 17 18 15 16 13 14 11 12
5

위 예시에서 20은 1칸 움직이면 되니 20을 맨 앞으로 옮기고 s는 5 - 1으로 4가 남게된다.

위치를 변경하고 나면 i가 1 증가하고 0번 인덱스는 이미 정렬되었다고 판단하여 
위치 변경 및 가장 큰 수 탐색에서는 더이상 해당 인덱스는 고려하지 않게 된다.

20 19 17 18 15 16 13 14 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 4

 

변경 후 이렇게 20이 가장 앞으로 오게 되고 0번 인덱스는 더이상 접근하지 않는다.

다음으로 똑같은 과정을 계속해서 진행해 보겠다.

 

20 19 17 18 15 16 13 14 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 4

 

20 19 18 17 15 16 13 14 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 3

20 19 18 17 15 16 13 14 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 3

 

20 19 18 17 16 15 13 14 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 2

 

20 19 18 17 16 15 13 14 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 2

 

20 19 18 17 16 15 14 13 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 1

 

20 19 18 17 16 15 14 13 11 12

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 1

 

20 19 18 17 16 15 14 13 12 11

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

s = 0

 

if (s == 0) break;

이후 해당 조건과 for문의 끝으로 인해 반복문은 종료되고
정렬된 배열을 출력하게 된다.