[12936] 줄 서는 방법

✔ 줄 서는 방법

[프로그래머스 12936]

문제 분석하기

n명의 사람이 있을 때, 줄을 서는 방법으로는 총 n * (n - 1) * ... * 1 (n!)의 방법이 존재하며

이때 (n - 1)!, (n - 2)! ... 만큼 같은 자리의 순서를 배정받게 되므로 이를 이용해 문제에 접근

 

예) n = 3, k = 5

배열은 0부터 시작하므로 k를 4로 감소하여 시작

 

1) 첫 번째 수 구하기

단위 = 전체 개수 / 요소 개수 = 6 / 3 = 2

구할 번호(k) / 단위 = 4 / 2 = 2

[1, 2, 3]

요소를 1개 구했으므로 구할 번호는 단위만큼 제외하여 4 % 2 = 0

 

2) 두 번째 수 구하기

단위 = 전체 개수 / 요소 개수 = 2 / 2 = 1

구할 번호(k) / 단위 = 0 / 1 = 0

[1, 2]

요소를 1개 구했으므로 구할 번호는 단위만큼 제외하여 2 % 2 = 0

 

3) 세 번째 수 구하기

단위 = 전체 개수 / 요소 개수 = 1 / 1 = 1

구할 번호(k) / 단위 = 0 / 1 = 0

[1]

요소를 1개 구했으므로 구할 번호는 단위만큼 제외하여 1 % 1 = 0

123 132

213 231

312 321

손으로 풀어보기

1. n을 이용해 줄을 서는 방법의 총 개수를 계산
   • n * (n - 1) * ... * 1 (n!)의 방법
2. n에서 k번째 방법을 계산하여 반환
   • k에서 각 자리수가 몇 번째 반복되고 있는지 구함

슈도코드 작성하기

n(사람의 수)
k(자연수)
answer(사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법)
list(1번부터 n번 번호)
count(줄을 서는 방법의 수)
for(i -> 1부터 n까지) {
    list.add(i)
    count *= i
}
자릿수를 맞추기 위해 k 감소
index(번호 위치)
while(index가 n보다 작을 동안) {
    count = count / (n - index)
    value(index번째 숫자) = (int) (k / count)
    answer[index++] = list.get(value)
    list.remove(value)
    k를 빠진 단위 만큼 변경
}
answer 반환

코드 구현하기

/**
 * 12936) 줄_서는_방법
 */
public class L014_12936 {
    // n(사람의 수)
    // k(자연수)
    public int[] solution(int n, long k) {
        // answer(사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법)
        int[] answer = new int[n];
        // list(1번부터 n번 번호)
        List<Integer> list = new ArrayList<>();
        // count(줄을 서는 방법의 수)
        long count = 1;
        // list와 count 계산
        for (int i = 1; i <= n; i++) {
            list.add(i);
            count *= i;
        }
        // 배열의 시작이 0이므로 이로 인한 자릿수를 맞추기 위해 k 감소
        k--;
        // index(번호 위치)
        int index = 0;
        // index가 n보다 작을 동안
        while (index < n) {
            // 단위(전체 개수 / 요소 개수) 구하기
            count = count / (n - index);
            // value(index번째 숫자)
            int value = (int) (k / count);
            // answer에 index번째 숫자 저장 후 삭제
            answer[index++] = list.get(value);
            list.remove(value);
            // k를 빠진 단위 만큼 변경
            k %= count;
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L014_12936 solution = new L014_12936();

        int n = 3;
        long k = 5;

        int[] result = solution.solution(n, k);

        System.out.println(Arrays.toString(result));
    }
}