2023년 12월 26일 알고리즘 문제풀이
문제
난이도
Lv.2
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math
def solution(n, k):
answer = []
arr = list(range(1,n+1))
while n>0:
tmp = math.factorial(n-1)
a = k//tmp
k = k%tmp
if k:
answer.append(arr[a])
arr.pop(a)
else:
answer.append(arr[a-1])
arr.pop(a-1)
n -= 1
return answer
순열에 정의를 알면 접근방식 자체는 그리 어렵지 않지만, 코드로 구현하는 게 꽤나 까다로웠다. 순열은 결국 앞에서부터 올 수 있는 경우의 수를 정해주고 곱하는 방식이다. 4명이 줄을 서는 방법은 4! = 4 x 3 x 2 x 1이다. 왜 이렇게 나오냐면, 맨 앞에 올 수 있는 후보는 4개 이고, 그 다음은 3개, 2개, 1개 이기 때문이다.
이걸 조금 바꿔서 생각해보면 맨 앞에 올 수 있는 4개 중 하나는 몇개의 경우를 가질까? 맨 앞에 A가 온다고 생각해보면, 뒤에 3자리에 B와 C와 D를 정렬하면 되니 3!일 것이다. 앞에 B, C, D 누가 오든 갯수는 같다. 따라서 4명이 정렬하는 것은 3!이 4번이니 3! x 4라고 할 수도 있다.
이 문제에는 두번째 접근 방법을 사용하면 된다. k번째라는 것을 통해 맨 앞에 올 사람이 누구인지 알 수 있다. n명이 줄을 설 때, 맨 앞에 누군가를 세우고 나서 생각해볼 경우는 (n-1)! 이다. k로 나누어서 몫을 구하면 몇번째인지 알 수 있고 이를 통해 맨 앞에 올 번호가 몇인지 알 수 있다. 그다음 k는 그만큼 빼줘야 한다. 여기선 나머지로 설정했는데 결국 같은 이치다. 맨 앞이 4번이라면 앞이 1번일 때부터 3번일 때까지는 이미 계산에서 제외했기 때문에 뺴주는 것이다.
4명이라고 가정하고 K가 15라고 가정하자. 4명이 줄을 서는 방법은 4! = 4 x 3! = 24이다. 모든 경우의 수는 순서대로, 1번이 맨 앞에 오는 경우 3! = 6 가지 + 2번이 맨 앞에 오는 경우 3! = 6 가지 + 3번이 맨 앞에 오는 경우 3! = 6 가지 + 4번이 맨 앞에 오는 경우 4! = 6 가지 의 합이다. 2번이 맨 앞에 오는 경우까지 모두 더하면 12개이고, 3번이 맨 앞에 오는 경우까지 더하면 18이다. 따라서 K는 15기 떄문에 이 사이에 있을 것이고 맨 앞에는 3일 것이라고 유추할 수 있는 것이다. 그럼 맨 앞이 3인 경우 에서 K-12 번째를 구하면 된다. 이 K-12 대신 K를 3!으로 나눈 나머지로 표시한 것이다. 결국 몇을 빼든 3!의 배수 중 가장 근접한 것으로 빼기 때문에 아무 문제가 되지 않는다.
만약 이 나머지가 0이라면 어떨까? 즉 위의 4!의 경우에서 6, 12, 18번쨰째를 구한다면? 12는 2가 맨 앞에 오는 경우 중 가장 마지막에 있는 case다. 하지만 몫을 따져보면 3이 맨 앞에 오는 경우로 편입되버린다. 이를 구분하기 위해 나머지 값이 0인지 아닌지에 따라 구분할 필요가 있다.
