프로그래머스 줄 서는 방법 C++

문제 풀이

n명의 사람이 일렬로 줄을 서고있다.

n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져있는데

사람이 줄을 서는 방법은 여러가지가 있다.

예를 들어 3명의 사람이 있다면

123 132 213 231 312 321 6가지가 있다.

사람의 수 n과 자연수 k가  매개변수로 주어지고, 사전 순으로 사람을 나열 하였을 때, k 번째의 경우의 수를 return 해라

 

문제 풀이

중복 불가 경우의 수 문제로

경우의 수는 n! 이다

 

완전 탐색을 하여 일일이 비교하기엔 너무 많은 경우의 수가 있기에

규칙을 찾았고

한자리수 마다 구해주면 더 빠르게 구할 수 있는 것을 알았다

k-1에 n의 팩토리얼 수를 위에서부터 나누어주면

첫번째자리부터 시작하여 끝의자리까지의 k번째 자리 수를 구할 수 있다.