백준 1083번, 소트 풀이

문제

백준 1083번

풀이

그리디 문제입니다.

 

$ i $를 $ 1 $부터 $ N $까지 순서대로 순회하면서, $ i $번째에 가능한 수 중 가장 큰 수를 넣어야 합니다.

 

모든 $ i ( 1 \leq i \leq N) $에 대하여 구간 $ [i, min(i + S, N)] $에 속하는 값 중 최댓값을 $ i $번째에 가져다 놓으면 됩니다. ($ S $는 사용한만큼 감소시킴)

 

$ N $의 범위가 50이므로, 막구현해도 TLE가 나지는 않습니다. 다만, 탐색 범위를 한번 더 확인해서 런타임 에러를 주의할 필요는 있습니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n, s;
	cin >> n;
	vector<int> vec(n);
	for (auto &i : vec) cin >> i;
	cin >> s;
	
	for (int i = 0; i < n && s > 0; i++) {
		int mx = -1, pos = 0;
		for (int j = i; j <= i + s && j < n; j++) {
			if (vec[j] > mx) {
				mx = vec[j];
				pos = j;
			}
		}
				
		for (int j = pos; j > i; j--) --s, swap(vec[j], vec[j - 1]);
	}
	
	for (const auto &i : vec) cout << i << " ";
}