[프로그래머스] 줄 서는 방법 Lv2

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

 

function solution(n, k) {
    const answer = [];
    const people = Array.from({ length: n }, (_, i) => i + 1);
    let caseNum = people.reduce((ac, v) => ac * v, 1)
    
    while (answer.length < n) {
        caseNum = caseNum / people.length;
        answer.push(...people.splice(Math.floor((k - 1) / caseNum), 1));
        k = k % caseNum;
    }

    return answer;
}

1. people = [1, 2, 3], caseNum = 3! = 6
2. 첫 번째 숫자 선택:
   • caseNum = 6 / 3 = 2
   • (k - 1) / caseNum = (5 - 1) / 2 = 2
   • people.splice(2, 1) → 3
   • answer = [3]
   • k = 5 % 2 = 1
3. 두 번째 숫자 선택:
   • caseNum = 2 / 2 = 1
   • (k - 1) / caseNum = (1 - 1) / 1 = 0
   • people.splice(0, 1) → 1
   • answer = [3, 1]
   • k = 1 % 1 = 0
4. 마지막 숫자 선택:
   • 남은 숫자는 [2], 그대로 answer에 추가
   • answer = [3, 1, 2]

최종 결과: [3, 1, 2]

---

정리

1. n!을 계산해서 각 자리에서 몇 번째 숫자를 고를지 정함.
2. (k-1) / caseNum을 계산해서 people 배열에서 선택할 숫자의 인덱스를 구함.
3. 선택한 숫자를 answer 배열에 추가하고, k 값을 갱신.
4. 모든 숫자를 선택할 때까지 반복.

 

1. n!을 이용한 그룹 크기 계산

n!은 n개의 숫자로 만들 수 있는 모든 순열의 개수를 의미해.
각 숫자가 맨 앞에 올 때마다 가능한 경우의 수는 (n-1)!이 돼.

예를 들어, n = 4일 때 사전순으로 가능한 모든 경우의 수를 보면:

 

1. [1, 2, 3, 4]
2. [1, 2, 4, 3]
3. [1, 3, 2, 4]
4. [1, 3, 4, 2]
5. [1, 4, 2, 3]
6. [1, 4, 3, 2]
----------------
7. [2, 1, 3, 4]
8. [2, 1, 4, 3]
9. [2, 3, 1, 4]
10. [2, 3, 4, 1]
11. [2, 4, 1, 3]
12. [2, 4, 3, 1]
----------------
13. [3, 1, 2, 4]
14. [3, 1, 4, 2]
15. [3, 2, 1, 4]
16. [3, 2, 4, 1]
17. [3, 4, 1, 2]
18. [3, 4, 2, 1]
----------------
19. [4, 1, 2, 3]
20. [4, 1, 3, 2]
21. [4, 2, 1, 3]
22. [4, 2, 3, 1]
23. [4, 3, 1, 2]
24. [4, 3, 2, 1]

 

여기서 보면,

• 1이 맨 앞에 오는 경우가 6개 (3! = 6)
• 2가 맨 앞에 오는 경우도 6개 (3! = 6)
• 3이 맨 앞에 오는 경우도 6개
• 4가 맨 앞에 오는 경우도 6개

즉, 맨 앞자리 숫자 하나를 정하면 나머지 숫자로 (n-1)!개의 조합을 만들 수 있어.

 

2. k를 이용해 첫 번째 숫자 찾기

우리는 k번째 순열을 찾아야 해.
각 숫자가 앞에 올 때마다 (n-1)!개의 경우가 존재하므로,

첫 번째 숫자는 (k-1) / (n-1)! 를 통해 몇 번째 그룹인지 찾을 수 있어.

예제) n = 4, k = 15

1. n! = 4! = 24
2. (n-1)! = 3! = 6 → 첫 번째 숫자가 고정될 때 가능한 경우의 수

k = 15이면  
(15 - 1) / 6 = 14 / 6 = 2번째 그룹 (0부터 시작하는 인덱스 기준)

 

즉, [1, 2, 3, 4] 중에서 세 번째 숫자인 3이 첫 번째 자리에 온다는 뜻이야.

 

3. 첫 번째 숫자를 제외한 나머지에서 k 갱신

첫 번째 숫자를 결정하고 나면,
남은 숫자에서 다시 (n-1)!을 이용해 두 번째 숫자를 찾는 방식이야.

1. 첫 번째 숫자로 3을 선택하면, 남은 숫자는 [1, 2, 4]
2. k = 15에서 이전 그룹(2번째 그룹)까지 계산된 숫자 개수(= 2 * 6 = 12) 를 뺀다.
3. 이제 n=3에서 k=3 번째 순열을 찾아야 하므로, 다시 (n-1)!을 이용해 두 번째 숫자를 찾음.
   • (n-1)! = 2! = 2
   • (3 - 1) / 2 = 1 → 남은 [1, 2, 4] 중 두 번째 숫자 2 선택
   • k = 3 - (1 * 2) = 1
4. 이제 n=2, 남은 숫자는 [1, 4]
   • (n-1)! = 1! = 1
   • (1 - 1) / 1 = 0 → 첫 번째 숫자인 1 선택
   • k = 1 - (0 * 1) = 1
5. 마지막 남은 숫자 [4] 선택.

결과: [3, 2, 1, 4] (15번째 순열)