[BOJ]1083-소트

1083

1차 시도

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

int S;

void reverseBubble(vector<int> &v)
{
	int size = v.size();
	int cnt = 0;
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size- i -1; j++)
		{
			if (v[j] < v[j+1])
			{
				int temp = v[j];
				v[j] = v[j+1];
				v[j+1] = temp;
				cnt++;

				if (cnt >= S)
				{
					return;
				}
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	vector<int> nums;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		nums.push_back(tmp);
	}

	cin >> S;

	reverseBubble(nums);

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

}

단순히 swap을 통해 내림차순으로 정렬했는데 1%에서 바로 탈락..

사전 뒷순이라 S가 여유있다면 큰 수를 먼저 끄집어 내야 한다.

결과 코드

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

int S;

void Sort(vector<int> &v)
{
	int size = v.size();
	for (int i = 0; i < size; i++)
	{
		int max = v[i];
		int maxIndex = i;

		for (int j = i+1; j < size; j++)
		{
			if (v[j] > max)
			{
				if (S >= j - i)
				{
					max = v[j];
					maxIndex = j;
				}
			}
		}

		for (int index = maxIndex; index > i; index--)
		{
			swap(v[index], v[index - 1]);
			S--;
		}
		if (S <= 0)
		{
			break;
		}
		
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	vector<int> nums;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		nums.push_back(tmp);
	}

	cin >> S;

	Sort(nums);

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

}

풀이를 보고 이해했는데 생각보다 간단했다.

해당 인덱스 이후의 숫자들 중 최대값을 찾고 S값과 비교하여 앞으로 끌고 오는 것.

참고자료

---

1083 c++ 풀이