[백준] 1083 소트

[백준] 1083 소트

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

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int n;
vector<int> vec;

void solve(int startIndex, int s) {
	//base case
	if((s == 0) || (startIndex == n-1)) return;

	//0~n-1인 배열에서 교환 횟수가 s개 남아있는 경우
	//index 최대 s인 원소를 맨 앞으로 이동시킬 수 있음

	//startIndex~n-1인 배열에서 교환 횟수가 s개 남아있는 경우
	//index 최대 startIndex + s인 원소를 startIndex로 이동시킬 수 있음

	//vec[startIndex] ~ vec[startIndex+s] 최대 원소 위치 찾기
	int maxNum = -1;
	int maxIndex = startIndex;
	for (int i = startIndex; i <= min(startIndex+s, n-1); ++i) {
		if (maxNum < vec[i]) {
			maxNum = vec[i];
			maxIndex = i;
		}
	}

	//최대 원소 startIndex로 이동
	for (int i = maxIndex; i > startIndex; i--) {
		swap(vec[i], vec[i - 1]);
		s--;
	}

	solve(startIndex + 1, s);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		vec.push_back(input);
	}

	int s;
	cin >> s;
	solve(0, s);

	for (int i = 0; i < n; ++i) {
		cout << vec[i] << " ";
	}
	return 0;
}

틀린 풀이

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n;

	vector<int> vec;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		vec.push_back(input);
	}

	int s;
	cin >> s;
	while (s--) {
		bool change = false;
		for (int i = 0; i < n - 1; ++i) {
			if (vec[i] < vec[i + 1]) {
				swap(vec[i], vec[i + 1]);
				change = true;
				break;
			}
		}
		if (!change) break;
	}

	for (int i = 0; i < n; ++i) {
		cout << vec[i] << " ";
	}
	return 0;
}

• 반례

input:
5
3 5 6 7 4
4

wrong:
3 5 6 7 4
5 3 6 7 4
5 6 3 7 4
6 5 3 7 4
6 5 7 3 4

answer:
3 5 6 7 4
3 5 7 6 4
3 7 5 6 4
7 3 5 6 4
7 5 3 6 4