[BOJ 백준] 순열의 순서(1722) C++

 

링크 : https://www.acmicpc.net/problem/1722

1722번: 순열의 순서

 

문제 설명 : 

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력 : 

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

 

예제 입력 : 

4
1 3

예제 출력 : 

1 3 2 4

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 순열의 순서 1722
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (21+3)
#define MOD (100000)

using namespace std;

int N;	
int q;  // 1인경우 k를 입력받기   // 2인경우 몇번째 순열인지 찾기
long long k;   // k번째 순열 구하기

long long factorial[MAX];
bool visit[MAX];

void makeFactorial();
void getKthPermutation(long long k);
long long nthPermutation(int arr[]);

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &q);

	// ** 팩토리얼을 활용해서 순열의 순서 구하기
	makeFactorial();

	if (q == 1) {
		scanf("%lld", &k);
		getKthPermutation(k);
	}
	else if (q == 2) {
		int arr[21];
		for (int i = 0; i < N; i++) {
			scanf("%d", &arr[i]);
		}
		printf("%lld", nthPermutation(arr));
	}
	return 0;
}

void makeFactorial() {
	factorial[0] = 1;
	for (int i = 1; i <= N; i++) {
		factorial[i] = factorial[i - 1] * i;
	}
}

void getKthPermutation(long long k) {
	int ans[MAX];

	for (int i = 0; i < N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			// ** 예외 조건 - 방문했으면 pass
			if (visit[j] == true) continue;

			// k > 팩토리얼이면 k - 팩토리얼
			if (factorial[N - i - 1] < k)
			{
				k -= factorial[N - i - 1];
			}

			// 팩토리얼 값이 k보다 크면 찾았다
			// ans 배열에 저장
			else
			{
				ans[i] = j;
				visit[j] = true;
				break;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		printf("%d ", ans[i]);
	}
}


long long  nthPermutation(int arr[]) {
	long long ans = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 1; j < arr[i]; j++)
		{
			// 1 ~ 해당 숫자까지 팩토리얼 더하기
			if (visit[j] == false) {
				ans += factorial[N - i - 1];
			}
		}
		// 방문배열 표기
		visit[arr[i]] = true;
	}
	return (ans + 1);
}
#endif