[Programmers] 줄 서는 방법

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12936#

코딩테스트 연습 - 줄 서는 방법

n의 최댓값이 10이었다면 next_permutation을 이용하여 쉽게 풀 수 있는 문제였을 것입니다.

하지만, n의 최대값이 20이고 20! 은 상당히 큰 숫자이기 때문에 브루트 포스로 접근하면 시간 초과가 발생하는 문제였습니다.

따라서, 팩토리얼을 이용하여 수학적으로 접근해야합니다.

 

알고리즘을 작성하면 아래와 같습니다.

1. 벡터에 1 ~ n까지 숫자를 순차적으로 입력

2. answerIdx를 줄의 자릿수라고 했을 때 (n - answerIdx)!를 구해주고

3. (k - 1)을 2번에서 구한 팩토리얼로 나눠 1번에서 도출한 벡터의 인덱스를 구하여 answerIdx에 위치할 숫자를 구합니다.

3.1 여기서 k가 아닌 k - 1을 팩토리얼로 나누는 이유는 인덱스가 0부터 시작하기 때문이고 이는 예시를 보면 알 수 있음

3.2 앞자리가 3인걸 알았을 때 다음 숫자의 k를 설정할 때 k에 대해  모듈러 연산을 하면 5 % 2 = 1, 6 % 2 = 0이 되면서 순서가 뒤바뀜. -> 따라서, k - 1에 대해 모듈러 연산한 값을 넣어줘야 함 

4. 남은 순열에 대해 k값을 다시 세팅해줘야 하는데 이는 기존 k에 대해 2번에서 구한 팩토리얼을 모듈러 연산한 값

4.1 4번을 진행하고 k 값이 0이라면 기존 k가 팩토리얼 값과 같았다는 것이었으므로 k 값을 팩토리얼로 수정

5. 2 ~ 4번 과정을 반복

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~