[백준 알고리즘] 1071번 소트 c++

a[i]+1 이 a[i+1]이 아닌 정렬 중 사전 순이 가장 빠른 결과를 출력하는 문제이다.

사전 순이 가장 빨라야 하므로 오름차순 정렬을 진행한다.

v[i]+1이 v[i+1]일 때, 2가지의 경우를 확인하면 된다.

 

1. v[i+1] 값과 v[n-1] 값이 같은 경우, v[i]값을 가지는 원소 중 가장 작은 index를 가지는 값과 v[i+1]를 swap한다.

(두 원소의 값 차이는 1이므로 v[start+1] ++, v[i+1] --로 swap을 진행함)

ex) 111222-> 211122 -> 221112 -> 222111

 

2. v[i+1]값과 다른 값은 가지는 원소중 가장 작은 index를 가지는 값과 v[i+1]를 swap한다.

ex) 1233334... -> 1243333....

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main(){
	int n;

	cin >> n;

	vector<int> v(n);

	int input;
	for(int i=0; i<n; i++){
		cin >> v[i];
	}

	sort(v.begin(), v.end());

	for(int i=0; i<n; i++){
		if(v[i]+1 == v[i+1]){
			int end = i+2;
			if(end != n){
				while(v[end] == v[i+1])
					end++;
			}

			if(end == n){
				int start = i-1;
				if(start >= 0){
					while(v[start] == v[i])
						start--;
				}

				v[start+1] ++;
				v[i+1] --;
			}
			else{
				int tmp = v[end];
				v[end] = v[i+1];
				v[i+1] = tmp;
			}
		}
	}


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