백준 1083 - 소트

 

 

문제 설명

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 내림차순으로 정렬할 때 S번만 이동시켰을 때의 결과를 구해야 한다.

 

문제를 읽어보면 버블 소트와 유사하다는 것을 알 수 있다.

버블 소트는 숫자 N개를 읽어 위치가 정해지지 않은 가장 큰 수의 위치를 정해가는 것이다.

하지만 해당 문제에서는 S번이라는 제약이 있기 때문에 가장 큰 수를 올바른 위치로 이동시키지 못할 경우가 생긴다.

그렇다면 이때 다음 큰 수를 찾으면 된다.

만약 S번 이하로 이동이 가능한 경우라면 해당 수를 이동시키는 것이 최적이다.

 

그럼 이를 구현하는 방법은 다음과 같다.

• 0번 인덱스부터 위치시킬 수를 찾는다.
• 찾은 수의 위치와 위치시킬 위치의 차이가 이동 횟수가 된다.
• 이동 횟수가 S보다 작다면 이동시킨다.
• 이동 횟수가 S보다 크다면 다음 큰 수를 찾는다.

 

예를 들어 보자.

5
5 3 4 7 2
2

S는 2로 주어졌다.

가장 큰 수인 7을 제일 앞으로 이동시키려면 3번의 이동이 필요하다.

따라서, 이는 불가능하다.

그다음 큰 수인 5를 제일 앞으로 이동시키려면 0번의 이동이 필요하다.

이는 가능하다.

이 과정을 통해 가장 앞자리는 5로 정해졌다.

이제 1번 인덱스에 위치할 수를 찾는 과정을 진행한다.

아직 S는 2이며 가장 큰수인 7을 찾을 수 있다.

7을 1번 인덱스로 이동시키기 위해서는 2번의 이동이 필요하다.

이는 가능하기 때문에 7을 1번 인덱스로 이동시키면 된다.

이제 S가 0이기 때문에 더 이상 이동 시킬 수 있는 수가 없다.

 

해당 문제는 swap이 아닌 이동임을 유의해야 한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, S;
vector<int> nums;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;
	
	cin >> N;
	nums.resize(N);

	for (int i = 0; i < N; i++)
	{
		cin >> nums[i];
	}

	cin >> S;

	for (int i = 0; i < N; i++)
	{
		if (S <= 0) break;

		set<int> checked;
		while (true)
		{
			int maxNum = 0;
			int idx = i;
			for (int j = i; j < N; j++)
			{
				if (nums[j] > maxNum && checked.count(nums[j]) == 0)
				{
					maxNum = nums[j];
					idx = j;
				}
			}

			if (idx - i <= S)
			{
				int num = nums[idx];
				nums.erase(nums.begin() + idx);
				nums.insert(nums.begin() + i, num);

				S -= (idx - i);
				break;
			}
			else
			{
				//다음 큰 수 찾기
				checked.insert(nums[idx]);
			}
		}
	}


	for (auto num : nums)
	{
		cout << num << " ";
	}

	return 0;
}

---