7991

 

inline static void __swap(int &t1, int &t2)
{
	int temp = t1;
	t1 = t2;
	t2 = temp;
}

static void __solution(vector<int> &list)
{
	int len = list.size();
	for (int i = 0; i < len - 1; i++)
	{
		if (list[i] + 1 == list[i + 1])
		{
			int j;

			for (j = i + 2; j < len && list[i + 1] >= list[j]; j++);
			if (j < len) //그런 숫자가 있음, 
			{
				__swap(list[i + 1], list[j]);
			}
			else //그런 경우가 없음.
			{
				__swap(list[i], list[i + 1]);
				for (int k = i; k > 0; k--)
				{
					if (list[k - 1] + 1 == list[k])
						__swap(list[k - 1], list[k]);
					else
						break;
				}
			}
		}
	}
}

static void solution(void)
{
	int N;
	cin >> N;

	vector<int> org(N);
	for (int i = 0; i < N; i++)
		cin >> org[i];
	sort(org.begin(), org.end());

	__solution(org);

	for (int i = 0; i < N; i++)
		cout << org[i] << " ";
	cout << endl;
}

먼저 입력받는 수열을 오름차순으로 정렬한다.

그래서 1 1 1 2 2 라는 수열이 있다 하면,

이 수열은 주어진 조건을 만족하지 못하게 된다.

1 1 1 은 만족하지만

1 1 (1 2) 에서 조건을 만족하지 못하게 된다. 그래서 2보다 큰 숫자가 2가 있는 위치에 와야 조건을 만족할 수 있다.

그러나 2보다 큰 숫자는 없다. 그래서 일단 두개의 자리를 바꾼다.

1 (1 2) 1 자리를 바꾸니 괄호안이 조건을 만족하지 못한다. 또 자리를 바꾼다. 이런식으로 조건을 만족할 때 까지 위치를 조정하게 된다.

 

이번에는 1 2 3 4 5 6 라는 수열을 대상으로 하겠다.

(1 2) 3 4 에서 괄호 안은 조건을 만족하지 못하므로 2 보다 큰 3을 2와 바꾼다.

1 3 2 (4 5) 6, 이제 4 5 가 조건을 만족하지 못한다. 5보다 큰 6을 5자리와 바꾼다.

1 3 2 4 6 5, 이제 모든 조건을 만족한다.