[BOJ 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개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
2가지 기능을 구현해야하는 문제이다. 각 기능을 하나씩 해결해보자.
1번 연산 :: k번째 순열 구하기
우선 숫자 $k$를 입력받는다. 그리고 case work를 우선 진행해보자.
- 현재 case에서 $N = 5$라고 가정하자
- 맨 앞자리가 $1$이라면, 그 수열은 $1 \leq k \leq 4!$ 이내에 있을 것이다
- 맨 앞자리가 $2$라면, 그 수열은 $4! + 1 \leq k \leq 2 \times 4!$ 이내에 있을 것이다
- 맨 앞자리가 $3$라면, 그 수열은 $2 \times 4! + 1 \leq k \leq 3 \times 4!$ 이내에 있을 것이다
- 맨 앞자리가 $4$라면, 그 수열은 $3 \times 4! + 1 \leq k \leq 4 \times 4!$ 이내에 있을 것이다
- 맨 앞자리가 $5$라면, 그 수열은 $4 \times 4! + 1 \leq k \leq 5 \times 4!$ 이내에 있을 것이다
일반화한다면, 구하는 수열의 맨 앞자리가 $a$라면 그 수열의 순번은 $(a-1) \times (N-1)! + 1 \leq k \leq a \times (N-1)!$ 사이에 있다는 의미가 된다. 그리고 이 과정은 수열의 길이가 $1$이 될 때까지 반복이 가능하다! 길이를 1씩 낮추는 반복을 통해 구하려는 수열의 가장 앞에 어떤 수가 등장해야하는지 판단하는 과정을 반복하여 정답 수열을 계산하자.
2번 연산 :: 주어진 순열이 몇번째인지 구하기
같은 방법으로 수열이 주어졌을 때 그 수열이 몇번째에 속하는지 알아보자. 가장 앞에 등장한 숫자에 따라 현재 수열이 어느 범위에 등장할지 판단할 수 있다. 역시 이 과정을 계속 반복하여 길이를 줄이고, 최종적으로 유일한 해가 등장하는 수열의 길이가 1인 경우까지 계산하여 정답을 도출할 수 있다.
소스코드
Github Link : Source Code
참고 알고리즘 :