https://programmers.co.kr/learn/courses/30/lessons/12936
-
flow
이거는 문제에 힌트가 있는게 ㅋㅋ.. 제한사항에서 k가 n! 이하의 자연수 조건이 있다. 고등 수학 많이 까먹었지만 n 개 집합에서 순서 세우는 것의 가짓수가 n! 라는 것을 기억해낼 수 있다.
이게 생각나자마자 바로 문제를 풀 방법이 떠올랐는데 k가 (n-1)! 보다 작으면 사전순서에 따라 맨첫번째 수는 무조건 1이 된다.. 왜냐면 1을 제외한 나머지 (n-1) 개의 순서를 다 못세웠기 때문.. 이런식으로 하나하나 자릿수를 정해내려갈 수 있다. 뭐 같은 논리로 (n-1)! < k < 2(n-1)! 면 2가 정해지는 식..
주의해야 할 점은 자릿수를 내려갈 때 (m-1)! 보다 작다고 m의 자리가 1이 아니라 남은 수중에서 가장 작은 수인 것을 명심.. 즉 order를 설정해놓고 사용된 수를 빼놔야 됨.
시간복잡도는 팩토리얼 계산하는 것이 가장 치명적
O(N^2) 이 되지만 N이 20이하 자연수라는 조건이 있어서 괜찮 -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A21.py
