문제

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

풀이

시간초과

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

int n;
vector<int> input; 

const int MAX = 10001; 
bool selected[MAX]; 
int arr[MAX]; 
bool checked = false; 

bool compareCurrentWithInput() {
	for(int i = 0; i < n; i++){ 
		if(arr[i] != input[i]) return false; 
	}
	return true; 
}

void dfs(int cnt){
	if(cnt == n){
		if(checked){
			for(int i = 0; i < n; i++){ 
				cout << arr[i] << " "; 
			}
			cout << endl; 
			exit(0); 
		} 
		
		// 입력으로 들어온 순열과 일치하는 경우 
		// 플래그 true로 설정 
		// return 하여 돌아갔을 때 플래그가 true이면 
		// 바로 다음 순열을 벡터에 따로 저장하고 정답 출력 
		if(compareCurrentWithInput()){ 
			checked = true; 
		}

		return; 
	}

	// n개 중에 n개 선택하기 (순열)
	for(int i = 1; i <= n; i++){ 
		if(!selected[i]){ 
			selected[i] = true; 
			
			arr[cnt] = i; // cnt번째로 선택된 원소 저장  
			dfs(cnt + 1);
		
			selected[i] = false; 
		}
	}
}

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

	cin >> n;

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

	dfs(0);

	if(checked){
		cout << "-1\n"; 
	}
	
	return 0;
}

순열의 모든 경우의 수를 구하다가, 입력과 일치하는 순열이 나오면 그 다음 순열을 바로 출력하는 식으로 구현했더니 시간초과가 발생했다.

전체 순열을 구하는 데 O(N!), 입력과 일치하는 순열인지 검사하는 데 O(N)이어서 결과적으로 O(N! * N)의 시간복잡도가 걸린다.

C++에서는 대략 1초에 1억 번의 연산을 수행하기 때문에, N! * N 이 1억을 넘지 않으려면 N은 최대 10이어야 한다. 이 문제는 N의 최대 1만이기 때문에 이 방법으로는 시간 초과가 발생할 수밖에 없다.

3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880
10! = 3,628,800
11! = 39,916,800

next_permutation

C++ STL의 next_permutation 함수를 사용하면 O(N)의 시간복잡도로 다음 순열을 구할 수 있다. 이전 순열을 구할 때는 prev_permutation을 사용하면 된다. 왜 O(N)의 시간복잡도가 걸리는지 궁금하다면 이 블로그 글을 참고하자!

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

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

	int n; 
	cin >> n;

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

	if(next_permutation(v.begin(), v.end())){
		for(int i = 0; i < n; i++){
			cout << v[i] << " ";
		}
		cout << endl; 
	}else{
		cout << "-1\n";
	}
	
	return 0;
}