[1722번] 순열의 순서 구하기(수학, 구현)

1722번: 순열의 순서

 

분석

4! = 24

3! = 6

2! =2

1! =1

제일 앞 자리에 사용할 수 있는 숫자 경우의 수 4가지, 다음 3가지, 다음 2가지, 다음 1가지

➔ N자리의 수로 만들 수 있는 순열의 모든 경우의 수 N!

1. K번째 순열 출력

1) 로직

1. 주어진 값(K)과 현재자리(N) -1에서 만들 수 있는 경우의 수를 비교
2. 1에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킴(순열의 순서를 1씩 늘림)
3. K가 더 작아지면 순열에 값을 저장하고 K를 K-(경우의 수 * (cnt-1))로 업데이트
4. 순열이 완성될 때까지 1-3을 반복

2) N=5, 30번째 순열

1. N=5이면, 총 5!개의 순열, 즉 120개의 순열이 있다.

맨 앞자리가 1인 순열은 1~24번째, 2인 순열은 25~48번째 ...

1인 순열 :  1-24
2인 순열 : 25-48
3인 순열 : 49-72
4인 순열 : 73-96
5인 순열 : 97-120

따라서 30번째 순열은 일단 맨 앞자리가 2임을 알 수 있다. (2)

 

2. N=4인 순열 중에서 6번째를 찾는것으로 바꿔 생각 할 수 있다. 

(5!에서 2인 순열 24개중 6번째를 찾는 것과 동일)

이때 N=4이면, 총 4!개의 순열, 즉 24개의 순열이 있다.

1인 순열 : 1-6
2인 순열(이미 사용)
3인 순열 : 7-12
4인 순열 : 13-18
5인 순열 : 19-24

따라서 6번째 순열은, 1인것과 같다 (2, 1)

 

3. N=3인 순열 중에서 6번째를 찾는것으로 바꿔 생각 할 수 있다. 

(4!에서 1인 순열 6개중 6번째를 찾는 것과 동일)

이때 N=3이면, 총 3!개의 순열, 즉 6개의 순열이 있다.

1인 순열(이미 사용)
2인 순열(이미 사용)
3인 순열 : 1-2
4인 순열 : 3-4
5인 순열 : 5-6

따라서 6번째 순열은, 5인것과 같다 (2, 1, 5)

 

4. N=2인 순열 중에서 2번째를 찾는것으로 바꿔 생각 할 수 있다. 

(3!에서 5인 순열 2개중 2번째를 찾는 것과 동일)

이때 N=2이면, 총 2!개의 순열, 즉 2개의 순열이 있다.

1인 순열(이미 사용)
2인 순열(이미 사용)
3인 순열 : 1
4인 순열 : 2
5인 순열(이미 사용)

따라서 2번째 순열은, 4인것과 같다 (2, 1, 5, 4)

 

같은 방법으로 끝까지 구해나가면 (2, 1, 5, 4, 3)을 구할 수 있다.

 

2. 입력된 순열의 순서

1) 로직

1. 현재 자릿수의 숫자를 확인하고 해당 숫자보다 앞 숫자 중 미사용 숫자 카운트
2. 미사용 숫자 갯수 * (현재자리 -1에서 만들 수 잇는 순열의 개수)를 K에 더함
3. 모든 자릿수에 관해 1-3을 반복

2) N=5 K =2,3,5,1,4

1. 맨 앞자리가 2이므로 25 ~ 48 에 포함되어 있다. +24

1인 순열 :  1-24
2인 순열 : 25-48
3인 순열 : 49-72
4인 순열 : 73-96
5인 순열 : 97-120

 

2. 그 다음 3이므로 다음 7 ~ 12 에 포함되어 있다. +6

1인 순열 : 1-6
2인 순열(이미 사용)
3인 순열 : 7-12
4인 순열 : 13-18
5인 순열 : 19-24

 

3. 그 다음 5이므로 다음 5 ~ 6 에 포함되어 있다. +4

1인 순열 :  1-2
2인 순열(이미 사용)
3인 순열이미 사용)
4인 순열 : 3-4
5인 순열 : 5-6

 

4. 그 다음 1이므로 다음 1 ~ 1 에 포함되어 있다. + 1

1인 순열 : 1
2인 순열(이미 사용)
3인 순열(이미 사용)
4인 순열 : 2
5인 순열(이미 사용)

 

5. 마지막 4는 자동으로 결정 : 위의 숫자들을 더하면 35

---

풀이

"""
1부터 N까지의 수 임의로 배열한 순열 경우의 수 N!
순열은 영문 사전의 정렬 방식과 비슷하게 정렬
N=3 -> 123 132 213 231 312 321

1. K가 주어지면 K번Wo 순열 구하기
2. 임의의 순열이 주어지면 이 순열이 몇 번째인지

자리수 N(1~20)
1 소문제 번호 -> K를 입력받음 1 3
2 소문제 번호 -> 임의의 순열을 나태는 N개의 수 2 1 4 2 4
"""
import sys
input = sys.stdin.readline

# 순열의 길이
n = int(input()) # 1~20

# n자리로 만들 수 있는 순열의 모든 경우의 수 n!
# 4자리=4!, 3자리=3!
# 자릿수에 따른 순열의 경우의수를 미리 계산한 팩토리얼 리스트
fList = [0] * 21
fList[0] = 1
for i in range(1, n+1):
    # 각 자리수에서 만들 수 있는 경우의수
    fList[i] = fList[i-1] * i

# 숫자 사용여부 리스트
visited = [False] * 21

# 출력 순열 리스트
s = [0] * 21

# 문제종류/순열데이터 입력 리스트
list = list(map(int, input().split()))

if list[0] == 1: # 순열 출력

    k = list[1] # 몇번째 순열을 출력할 지
    for i in range(1, n+1):
        cnt = 1 # 해당 자리에서 몇 번째 숫자를 사용해야 할 지 정하는 변수
        for j in range(1, n+1):
            if visited[j]:  # 이미 사용한 숫자 계산 X
                continue
            if k <= cnt * fList[n-i]: # 맨 앞자리가 몇인 순열에 속하는지
                k -= (cnt-1) * fList[n-i] # k = k- ((cnt-1) * 경우의 수)
                # 현재 자리에 j값 저장
                s[i] = j
                visited[j] = True
                break
            cnt += 1
    # 순열 출력
    for i in range(1, n+1):
        print(s[i], end=" ")

else: # 순열의 순서 출력

    k = 1 # 순열의 순서 저장
    for i in range(1, n+1):
        cnt = 0
        # 현재 자릿수의 숫자보다 앞 숫자 중 미사용 숫자 카운트
        for j in range(1, list[i]):
            if not visited[j]:
                cnt += 1
        # 미사용 숫자 개수 * (현재자리 -1 에서 만들 수 있는 순열의 개수)를 더함
        k += cnt * fList[n-i]
        visited[list[i]] = True

    print(k)