[프로그래머스] 줄 서는 방법 (연습문제)

programmers.co.kr/learn/courses/30/lessons/12936?language=java

코딩테스트 연습 - 줄 서는 방법

2020-12-12

---

import java.util.ArrayList;
import java.util.Arrays;
 
public class Solution12936 {
    public static int n;
    public static long k; // test용
    public static ArrayList<Integer> list;
    public static long fact[], fa;
 
    public static void init(int num) { // factorial 계산
        fact[1] = 1;
        fact[2] = 2;
        
        for(int i = 3; i <= num; i++) {
            fact[i] = i * fact[i-1];
        }
    }
 
    public static void main(String[] args) {
        n = 4;
        k = 10;
        int answer[] = new int[n];
        fact = new long[n+1];
        list = new ArrayList<>();
        for(int i = 1; i <= n; i++) list.add(i);
        init(n);
        
        long start = k-1; //k가 한 블럭의 마지막일 경우 다른 블럭으로 잡힘 
        for(int i = 1; i < n; i++) {
            int idx = (int) (start / fact[n-i]); 
                answer[i-1] = list.get(idx);
                list.remove(idx);
                start %= (fact[n-i]);
        }
        
        answer[n-1] = list.get(0);
        System.out.println(Arrays.toString(answer)); // test용
    }
}

 

#문제풀이

n == 4이고 k == 10 이라고 가정해본다. 줄 설 수 있는 숫자들을 나열해보면 다음과 같다. 그리고 규칙을 발견할 수가 있다. 첫째자리 기준으로 크게 두 블럭으로 나눌 수 있다. 또, 하나의 블럭(6개)을 쪼개보면, 2개씩, 1개씩, 1개씩 나눌 수 있다. 마지막을 제외하고 6, 2, 1 숫자를 보면 각각 3!, 2!, 1!을 의미함을 알 수 있다. 

1234
1243
1324
1342
1423
1432 

-------
2134
2143

2314

2341 ---> k == 10

2413
2431 

 

그 다음 각 자리가 갖을 수 있는 index 값을 찾아야하는데, 처음에는 k를 시작점으로 잡고 했었다. 하지만 k가 6일때, k/6을 하면 1이 나오고, 그러면 저 규칙대로 정답을 만들 수 없었다. 그래서 처음 기준점을 k-1로 잡았고, (k-1) / factorial[n-1] 나눈 값을 index로 생각하였다. 그렇게 하면 파란색 부분 한 블럭의 첫 번째 숫자를 구할 수 있다. 이것을 n-1만큼 반복했고 맨 마지막에 list에 남은 값은 answer의 맨 마지막 값으로 넣었다.

 

n == 4, k == 10일때

list	start	fact[n-i]	answer (index)
1, 2, 3, 4	9 (k-1)	6 (3!)	2 (1)
1, 3, 4	3 (9 %= 3)	2 (2!)	3 (1)
1, 4	1 (3 %= 2)	1 (1!)	4 (1)

그리고 마지막으로 남은 1을 넣어주면 [2, 3, 4, 1] 을 출력할 수 있다.