1071번 : 소트

https://www.acmicpc.net/problem/1071

1071번: 소트

문제는 단순하다. A[i] + 1 != A[i+1] 을 만족하도록 모든 수를 다시 배치하는 것이다.

 

아이디어 : 

두 수를 비교해서 위치를 바꾸는 일반적인 정렬 방식은 사용하지 않는다.
수들을 처음부터 하나하나 다시 배치하는 아이디어로 접근한다.

우선, 수를 하나 택한다고 생각해보자. 이 수를 뺀 나머지 수들을 이용해서 절대로 배열을 완성할 수 없다면, 그 수를 택할 수 없다.
반대로 말하면 -> 수를 하나 택하고, 이 수를 뺀 나머지 수들을 이용해서 배열을 완성할 수 있다면, 그 수를 택할 수 있다.
단, 택하는 수는 그 이전에 택했던 수+1이 아니어야 한다.

말장난 같지만 이걸로 그리디 알고리즘을 사용할 수 있다.

우선 정렬해두고, 작은 수부터 해당 수를 택한다고 가정 한 후에, 남은 수들로 배열을 완성할 수 있는지 여부를 조사한다.
남은 수들로 배열을 완성할 수 없는 경우는 택한 수와 다른 수가 하나밖에 없고, 그 수가 택한 수+1인 경우이다.
예시를 들면, 1 1 1 1 1 2 2 2 2 2에서 1을 택한다고 가정하자. 그럼 택한 수와 다른 수가 2 하나이고, 이 수가 택한 수+1이므로 1을 택할 수 없다.

 

구현 : 

먼저 배열을 정렬한 후에 작은 수부터 그리디로 택할 수를 결정한다.

 

코드 : 

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int visit[51];
int main(){
	int N; cin>>N;
	for(int i=0; i<N; ++i){
		int a; cin>>a; v.push_back(a);
	}
	sort(v.begin(), v.end());
	int prev=-2;
	for(int i=0; i<N; ++i){
		for(int j=0; j<N; ++j){
			if(visit[j]) continue;
			if(prev+1==v[j]) continue;
			bool flag=true;
			for(int k=0; k<N; ++k){
				if(visit[k]) continue;
				if(k==j) continue;
				if(v[k]==v[j]) continue;
				if(v[k]!=v[j]+1) flag=false;
			}
			if(flag) continue;
			visit[j]=1;
			cout << v[j] << " ";
			prev=v[j];
			break;
		}
	}
	for(int i=0; i<N; ++i){
		if(!visit[i]) cout << v[i] << " ";
	}
	cout << '\n';
}

 

여담 : 

처음엔 dfs로 접근했었다. 당연히 시간초과가 났고, 좀 더 단순히 생각했더니 맞았다.