BOJ 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개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.
소스코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();//N까지의 수
int mode = sc.nextInt();//1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다.
long[] f = new long[N+1];
boolean[] bool = new boolean[N+1];
f[0] = 1;//팩토리얼구하기
for(int i=1; i<=N; i++) {
f[i] = f[i-1]*i;
}
if(mode == 1) {//1이니 k를 입력받고,
long k = sc.nextLong();
int[] array = new int[N];
for(int i=0 ; i<N ; i++) {
for(int j=1; j<=N; j++) {
if(bool[j] == true) continue;
if(f[N-i-1] < k) {
k -= f[N-i-1];
}else {
array[i] = j;
bool[j] = true;
break;
}
}
}
for(int i=0; i<N; i++) {
System.out.print(array[i]+" ");
}
}else {//1이 아닌 다른수 이니. 2이니 임의의 순열을 나타내는 N개의 수 입력
int[] array = new int[N];
for(int i=0; i<N; i++) {
array[i] = sc.nextInt();
}
long answer = 1;
for(int i=0; i<N; i++) {
for(int j=1; j<array[i]; j++) {
if(bool[j] == false) {
answer += f[N-i-1];
}
}
bool[array[i]] = true;
}
System.out.println(answer);
}
}
}
이번 문제의 핵심
long타입으로 값을 받는 경우를 고려해야합니다.
Factorial이 20까지 가능한데 숫자의 크기가 커질수록 integer의 값으로는 받아내지 못합니다.
따라서 Long 타입으로 변경해줍니다.
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int mode = sc.nextInt();
long[] f = new long[N+1];
boolean[] bool = new boolean[N+1];
f[0] = 1;//팩토리얼구하기
for(int i=1; i<=N; i++) {
f[i] = f[i-1]*i;
}
입력부 입니다.
mode는 조건) 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. 를 위해 정수를 받습니다.
f[]는 팩토리얼의 범위 때문에 long을 사용합니다.
팩토리얼 공식처럼 값을 넣어줍니다.
if(mode == 1) {
long k = sc.nextLong();
int[] array = new int[N];
for(int i=0 ; i<N ; i++) {
for(int j=1; j<=N; j++) {
if(bool[j] == true) continue;
if(f[N-i-1] < k) {
k -= f[N-i-1];
}else {
array[i] = j;
bool[j] = true;
break;
}
}
}
for(int i=0; i<N; i++) {
System.out.print(array[i]+" ");
}
mode의 값이 1입니다.
1인 경우 k(1≤k≤N!)를 입력받습니다.
array[]는 숫자 N의 크기만큼 만들어줍니다.
만약 bool[j]가 true라면 순열에 이미 존재하는 숫자이므로 넘어갑니다.
팩토리얼 값이 k보다 작으면 k에서 팩토리얼 값을 빼줍니다.
또는 팩토리얼 값이 k보다 크면 해당하는 원소의 숫자를 찾은 것입니다.
a[i]에 저장하고 순열에 존재하는 숫자를 체크합니다.
else {
int[] array = new int[N];
for(int i=0; i<N; i++) {
array[i] = sc.nextInt();
}
long answer = 1;
for(int i=0; i<N; i++) {
for(int j=1; j<array[i]; j++) {
if(bool[j] == false) {
answer += f[N-i-1];
}
}
bool[array[i]] = true;
}
System.out.println(answer);
}
}
1이 아닌 다른수 이니. 2이니 임의의 순열을 나타내는 N개의 수 입력 받습니다.
1부터 해당하는 원소까지 팩토리얼 값을 늘려가며 더해줍니다.
순열에 존재하는 숫자는 있다고 true처리 합니다.
끝이난다면 결과를 출력합니다.