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

문제

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

프로그래머스

 

풀이코드

public int[] solution(int n, long k) {      //줄 서는 방법
    int[] answer = new int[n];
    int idx = 0;                            //index값
    long fac = 1;                           //factorial
    List<Integer> list = new ArrayList<>();
    k--;                                    //k값에서 1을 빼준다 자세한 풀이는 블로그에 기재
    for (int i = 1; i <= n; i++) {          //ArrayList에 1~n까지 차례대로 추가해주고 factorial에 곱해줌
        list.add(i);
        fac *= i;
    }
    while(n>0){                             //자세한 풀이는 블로그에 기재
        fac /= n;
        answer[idx++] = list.get((int)(k/(fac)));
        list.remove((int)(k/fac));
        k %= fac;
        n--;
    }
    return answer;
}

 

풀이코드 설명

1.

int[] answer = new int[n];
int idx = 0;                            //index값
long fac = 1;                           //factorial
List<Integer> list = new ArrayList<>();
k--;

1-1. answer배열에 어차피 k번째 방법을 넣어야 되니까 사람수인 n만큼 배열을 생성

1-2. answer[idx] 이런식으로 index값을 대체해줄 변수 idx를 생성

1-3. 사람 수 n에 따라 줄을 세울 수 있는 총 경우의 수를 저장할 변수 fac 생성

1-4. k--를 한 이유는 나중에 설명

 

2.

for (int i = 1; i <= n; i++) {          //ArrayList에 1~n까지 차례대로 추가해주고 factorial에 곱해줌
    list.add(i);
    fac *= i;
}

2-1. ArrayList에 1부터 사람 수인 n까지 차례대로 값을 넣어준다.

2-2. 사람을 줄 세울 수 있는 총 경우의 수를 fac에 넣어준다.

 

3.

while(n>0){                            
    fac /= n;
    answer[idx++] = list.get((int)(k/(fac)));
    list.remove((int)(k/fac));
    k %= fac;
    n--;
}

3-1.

우선 예를 들어 사람이 3명이라고 가정을 하면 줄을 세울 수 있는 경우의 수는 총 6가지이고 일일히 나열하면

[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]가 되는데 여기서 제일 앞사람이 바뀌는 주기는

총 경우의 수인 6에서 사람의 수인 3을 나누면 된다.

왜냐하면 앞사람이 1,2,3 이렇게 3명 밖에 없고

1로 시작되는 줄

2로 시작되는 줄

3로 시작되는 줄

이렇게 크게 3줄로 나뉘는데 그러면 총 경우의 수가 6이니까 한줄당 2개의 경우의 수를 차지하므로

총 경우의 수인 6/3을 하면 앞사람이 바뀌는 주기를 알 수 있다.

그래서 fac/n에서 제일 앞사람이 누군지 알 수 있고 여기서 fac/n의 결과에서 마찬가지의 원리로

(fac/n)/(n-1) 이렇게 n-1로 나누면 제일 앞사람 뒤의 사람이 누군지 알 수 있다.

그래서 위의 코드에서 fac /= n과 n--을 각각 해주는 것이다.

 

3-2. 

answer[idx++]은 그냥 answer 배열의 처음부터 차례대로 값을 넣기위해 저렇게 쓴 것이고

그 뒤의 list.get(k/fac)은 list에 1~n까지 차례대로 숫자가 들어가있는데

 

예를 들어 n이 3일때,

 list에 이런 식으로 저장이 된다.

근데 우린 list[0]의 값이 1이되고 list[1]의 값이 2가 되므로

만약 우리가 구하려는 k번째 사람이 어디있는지 찾을 때,

예를 들어 k = 6이면, 6/2를 했을 때, 3인데

우리가 원하는 3이 나오는게 아니라 index값으로 인식을 해서 

IndexOutOfBoundsException과 같은 오류가 발생하게 된다.

이런 불상사를 막기 위해 일부러 k값을 1줄여서 계산하게 되면

k=6일때, 5/2 => 2.5 (int형으로 형변환)=> 2가되어 우리가 원하는 list[2]인 3이 나온다.

 

3-3.

그렇게 사람을 1명 줄 세웠으면 똑같은 사람을 다시 다른 위치에 줄을 세울 수 없으므로

목록에서 제거를 해준다.

list.remove((int)(k/fac));

 

3-4.

그리고 위에서 fac/n의 단위로 앞에 서는 사람들이 바뀌니까 k번째 서는 사람을 찾을 때에도 이것을 반영하여

k %= fac으로 k를 계속 수정해준다.

 

이렇게 계속 반복하는데 n이 0이되면 더 이상 사람이 없는 것이므로 반복문을 끝낸다.