[Algorithm Problem] 소트 (BAEKJOON: 1083)

소트 (BAEKJOON: 1083)

이 문제는 Selection Sort(선택 정렬) 방법을 조금 응용한 문제였다. 문제 풀이보다 해석이 어려운 문제라고 생각한다. 쉽게 설명하자면 크기가 N인 배열을 내림차순으로 정렬하는 과정에서 삽입될 자리와 선택된 자리의 거리 합이 S를 넘지 않도록 만드는 문제가 될 수 있다.

풀이

#include<iostream>

using namespace std;

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, arr[50], S;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	cin >> S;

	for (int target_pos = 0; target_pos < N; target_pos++) {
		int maxVal = arr[target_pos], maxIdx = target_pos;

		// find max value and index
		for (int t = target_pos + 1; t < N; t++) {
			if (maxVal < arr[t] && S - (t - target_pos) >= 0) {
				maxVal = arr[t];
				maxIdx = t;
			}
		}

		for (int i = maxIdx; target_pos < i; i--) {
			arr[i] = arr[i - 1];
		}

		arr[target_pos] = maxVal;
		S -= (maxIdx - target_pos);
		
		if (S <= 0) break;
	}

	for (int i = 0; i < N; i++) cout << arr[i] << ' ';

	return 0;
}