백준 1083: 소트

문제 요약

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

문제 분류

• 그리디 알고리즘
• 정렬

문제 풀이

단순히 버블 정렬을 생각하기 쉽지만, 가능한 큰 수를 가장 앞으로 가져오는 게 목적이다. 0번째 자리의 수를 S가 허용하는 내에서 가능한 한 크게 만들고, 그다음은 1번째 자리, 그다음은 2번째 자리...순으로 채워 나가면 된다.

0번째 자리에서 시작하므로 i는 0부터 시작, i는 가능한 큰 수로 바뀌어야 할 현재 위치를 말한다. i + 1부터 n까지 가장 큰 수를 찾고, 해당 수가 S의 안에 가능한 지 파악한다. 해당 큰 수가 m번째 라고 할 경우, i번째 수와 m번째 수를 차례로 교환하는 횟수가 S이하라면 가능, 초과라면 불가능이다. 불가능한 경우에는 해당 m번째의 수를 impo[]로 불가능하다고 표시한다. 가능한 경우에는 impo[]을 초기화하고, m부터 i까지 swap하면서 m번째의 수를 i번째로 밀어주고, S를 차감해준다. 그 후, i를 1더하여 다음 인덱스로 이동한다.

만약 v[i]와 in이 같은 경우는 이미 v[i]에 최대값이 들어간 경우이므로, impo[]을 초기화하고 i를 1 더한 뒤, for문을 지속해준다(conitnue).

그렇게 i가 모든 배열의 탐색을 마치거나, S가 0이 되면, for문을 나오고 출력하게 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

bool impo[1000001];

int main()
{
	int n, s, in, m;
	vector<int> v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		v.push_back(in);
	}
	cin >> s;
	for (int i = 0; i < n && s;) {
		in = v[i];
		for (int j = i + 1; j < n; j++) {
			if (v[j] > in && !impo[v[j]]) {
				in = v[j];
				m = j;
			}
		}
		if (in == v[i]) {
			i++;
			memset(impo, false, sizeof(impo));
			continue;
		}
		if (m - i <= s) {
			s -= m - i;
			memset(impo, false, sizeof(impo));
			for (int j = m; j > i; j--)
				swap(v[j], v[j - 1]);
			i++;
		}
		impo[in] = true;
	}
	for (auto& it : v)
		printf("%d ", it);
	return 0;
}