BOJ 10974 (모든 수열)

• 문제
  N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
  
  
• 출력
  첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

#include<iostream>
#include<vector>
using namespace std;
int N;
vector<int> perm;
bool checked[9];

void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input() {
	cin >> N;
}

void permutation() {
	if (perm.size() == N) {
		for (int i = 0; i < perm.size(); i++) {
			cout << perm[i] << ' ';
		}
		cout << '\n';
	}

	for (int i = 1; i <= N; i++)
	{
		if (checked[i]) {
			continue;
		}
		checked[i] = true;
		perm.push_back(i);
		permutation();
		perm.pop_back();
		checked[i] = false;
	}
}

int main() {
	fast_io();
	input();
	permutation();
	return 0;
}

   입력의 최대 크기가 8이고 1초가 주어진다면 완전탐색(Brute Force) 문제 + BackTracking 기법을 사용하는 문제이다. (그냥 외워버리자)

N과 M (1) 문제(15649번)와 유사한 문제로 push와 pop 포함된 숫자의 체크여부와 해제를 적절하게 해주기만하면 쉽게 해결할 수 있다

시간 복잡도 : O(N!)

숏코딩

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int n,a[10]={1,2,3,4,5,6,7,8};
	scanf("%d",&n);
	do{
			for(int i=0;i<n;i++)
		printf("%d ",a[i]);
		printf("\n");
	}while(next_permutation(a,a+n));
}

C++ STL의 algorithm 헤더에 있는 next_permutation을 사용하면 훨씬 간결하게 짤 수 있는 것 같다.

next_pemutation

• 오름차순으로 정렬된 값을 가진 컨테이너로만 사용 가능
• default로 < 연산자를 사용해 순열을 생성
• 중복이 있는 원소들은 중복을 제외하고 순열을 생성해준다

boolean next_permutation(BidirectionalIterator first, BidirectionalIterator last);

배열의 시작과 끝을 반복자 인자로 받고 현재 나와있는 순열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 True를 반환 | 다음 순열이 없다면 false를 반환