[Lv3] 줄 서는 방법

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

 

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

---

입출력 예

n	k	result
3	5	[3,1,2]

 

입출력 예시 설명

입출력 예 #1
문제의 예시와 같습니다.

 

 

---

 

k번째가 어떻게 이루어져 있는가..인데

 

예전 문제와 비슷합니다.

[Coding Quiz/programmers] - [Lv2] 124 나라의 숫자

 

단, 124나라의 숫자는 자릿수가 다음으로 넘어가도 여전히 같은 숫자를 쓸 수 있지만,

이번 문제는 한 번 쓴 숫자는 버려지게 됩니다.

 

전체 흐름은 비슷하게 갑니다.

 

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

를 볼 때, 총 6개를 3으로 나누면 2고, 2씩 3덩이가 되는 것.

다음 자릿수로 넘어가면서 6개가 아니라 2개가 되고.. 이런 조각(slice)내어 조각들을 활용하는 방식으로요.

 

 

LinkedList<Integer> list = new LinkedList<>();
for(int i=1;i<=n;i++) list.add(i);
int[] answer = new int[n];
long total = factorial(n);

1~n까지의 수를 제거하면서 쓸 것인데,

제거하면서 그 때 그 때의 순서가 필요합니다.(1,2,3에서 1을 쓰고 나면 2,3이라 그 다음엔 제일 처음이 2인걸 알 수 있게)

제거해나갈 것이니, LinkedList를 쓰겠습니다.

 

경우의 수 상 총 갯수는 팩토리얼이 됩니다.

public long factorial(int n) {
    long answer = 1L;
    for(int i=2;i<=n;i++) answer*=i;
    return answer;
}

 

[1, 2, 3, 4] / 01

[1, 2, 4, 3] / 02

[1, 3, 2, 4] / 03

[1, 3, 4, 3] / 04

[1, 4, 2, 3] / 05

[1, 4, 3, 2] / 06

───────

[2, 1, 3, 4] / 07

[2, 1, 4, 3] / 08

[2, 3, 1, 4] / 09

[2, 3, 4, 1] / 10

[2, 4, 1, 3] / 11

[2, 4, 3, 1] / 12

───────

[3, 1, 2, 4] / 13

[3, 1, 4, 2] / 14

[3, 2, 1, 4] / 15

[3, 2, 4, 1] / 16

[3, 4, 1, 2] / 17

[3, 4, 2, 1] / 18

───────

[4, 1, 2, 3] / 19

[4, 1, 3, 2] / 20

[4, 2, 1, 3] / 21

[4, 2, 3, 1] / 22

[4, 3, 1, 2] / 23

[4, 3, 2, 1] / 24

 

17번째인 [3, 4, 1, 2]를 구하는 걸로 해보겠습니다.

처음 total은 4!=4*3*2*1=24네요.

24를 n=4로 나누면, 6이 됩니다. 6개가 1slice로, 총 4slice가 생겨날겁니다.

 

01~06 → 1,

07~12 → 2,

13~18 → 3,

19~24 → 4

가 첫칸에 올 숫자들입니다. slice인 6으로 나눈 수라고 하기엔 살짝 걸리죠?

01~05는 6으로 나누면 0이지만, 06은 1이고,

07~11은 6으로 나누면 1이지만, 12는 2이고,... 1씩 빼줍니다.

 

00~05 → 0,

06~11 → 1,

12~17 → 2,

18~23 → 3

이제 6으로 나눈 숫자가 그룹별로 통일되어 있습니다.

매칭된 숫자에 1을 더해주냐 싶지만,

list에 [1,2,3,4] 순으로 되어있으니, 그냥 index용으로 바로 쓰면 됩니다.

 

정답 배열 answer[]의 처음에는 list.remove(순서)로 해당 숫자를 빼서 쓰면서 사라집니다.

17번째(17-1=16)니 6으로 나누면 2, list.remove(2)로 3이 나와서 적히고 사라졌겠네요.

 

이제 3이 앞에 오는 slice 하나만 보면 되니, total은 slice(=6)가 됩니다.

k번째는 slice상에서 몇번째인지 확인해보면, k%slice로 1,2,3,4,5,6번째를 구할 수 있습니다.

6번째는 나머지가 0이 되니까 나머지가 0일 때만 slice(=6)으로 치환.

 

total = slice.

즉, 루프가 돌 때 k=k%slice (0이면 slice로 치환),

숫자 한개를 소모했으니, n--;

정답 배열용 index++;

 

이제 다음번엔 총 6개를 n=3으로 나누면 2. 1slice에 2개씩 든 3덩이로 나뉩니다.

17번째는 이번 루프에서는 5번째가 되어있고,

(5-1)/2=2로, [1,2,4] 중 해당하는 4가 꺼내질겁니다.

total은 2가 되고,

k는 5%2=1.

n은 2.

 

이제 다음번엔 총 2개를 n=2로 나누면 1. 1slice에 1개씩 든 2덩이로 나뉩니다.

(1-1)/1=0이니, [1,2] 중 해당하는 1을 꺼낼 것.

total은 1이 되고,

n은 1.

list에는 이제 [2] 밖에 남지 않았으므로 자연스럽게 2가 다음에 올 것.

즉, 루프는 n>1까지만 돌고, 루프 밖에서 마지막 남은 1개를 답의 마지막 칸에 넣으면 끝.

(처음부터 순서대로 3,4,1,2가 꺼내졌고, 위를 보면 17번째는 [3,4,1,2]가 맞다.)

 

int index = 0;
while(n>1) {
    long slice = total/n;
    int now = (int)((k-1)/slice);
    answer[index] = list.remove(now);
    k = k%slice;
    if(k==0) k=slice;
    total = slice;
    index++;
    n--;
}
answer[index] = list.remove(0);
return answer;