# 프로그래머스 : 줄 서는 방법 (Level 5)

[문제]

N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다.

이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에... 서 있는 상태를 나타냅니다.

이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다.

예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다.

• 1번째 방법은 [1,2,3]
• 2번째 방법은 [1,3,2]
• 3번째 방법은 [2,1,3]
• 4번째 방법은 [2,3,1]
• 5번째 방법은 [3,1,2]
• 6번째 방법은 [3,2,1]

이 때 K가 5이면 [3,1,2]가 그 방법입니다.

사람의 수 N과 순서 K를 입력받아 K번째 방법으로 줄을 세우는 setAlign 함수를 완성해 보세요. 예를 들어 setAlign(3,5)를 입력받는다면 [3,1,2]를 리턴해주면 됩니다.

[풀이]

식은 굉장히 빨리 찾아냈는데, 코딩하는데 시간이 은근히 오래 걸렸다.
사실 얼떨결에(?) 테스트를 통과했다고 해서, 조금은 꺼림직하기는 하지만;;

우선 이론적으로 알아낸 식은 정확했다.
전체 인원수 N, 그 중에서 순서를 Cnt라고 할 때,
Cnt / (N!/N) = 해당 인덱스의 순서번호가 된다.

예를 들어서, 4명이 있고 순서가 15라고 가정할 때

1. [v][ ][ ][ ]
1. 15 / (4!/4) = 2.xx 가 되므로, 1번째 열에는 2보다는 큰 3이 오게 된다.
2. 15 % (4!/4) = 3이므로, 2번째 열에서는 3번째 순서가 된다.
2. [3][v][ ][ ]
1. 3 / (3!/3) = 1.xx 가 되므로, 2번째 열에는 1보다는 큰 2가 오게 된다.
2. 3 % (3!/3) = 1이므로, 3번째 열에서는 1번째 순서가 된다.
3. [3][2][v][ ]
1. 1 / (2!/2) = 1이고, 나머지는 0이기 때문에 첫번째 열의 숫자가 된다.

그러므로 이를 식으로 표현하면,

int factorial(int num) {

return (num == 1) ? 1 : num * factorial(num - 1);

}

vector<int> setAlign(int n, long long cnt)

{

vector<int> answer;

vector<int> check;

vector<int> sorting;

int index = 0;

int remain = 0;

int count = 0;

// Initialize

for (int i = 0; i<n; i++) check.push_back(i + 1);

for (int i = n; i>0; i--) {

index = cnt / (factorial(i) / i);

remain = cnt % (factorial(i) / i);

if (remain > 0) {

answer.push_back(check.at(index));

check.erase(check.begin() + index);

}

else {

sort(check.begin(), check.end());

if (i == 1) {

for (int j=0; j<check.size(); j++) {

answer.push_back(check.at(j));

}

}

}

cnt = remain;

}

return answer;

}

식을 세우는 것에는 자신감이 많이 붙었는데, 머리속에 든 내용을 코드화 하는 연습은 계속 해야할 것 같다.