프로그래머스 Lv.3) 줄 서는 방법

줄 서는 방법

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

풀이

오랜만에 문제가 잘 풀리는 날이다. 문제를 보고 규칙을 찾기위해 머리를 굴렸다. 그러면서 생각한게, 답이 될 앞쪽 인덱스부터 몇 번째 순서까지 어떠한 수가 오는지 규칙을 찾았다. 우선 예제의 n이 너무 작다고 생각해서, n=5 일 때를 가정하고 생각했다.

n=5 일때는 answer 배열의 크기는 5가 되고, 0~4 idx 까지 알맞은 순서를 찾아야 한다.

우선 규칙에 따라 모든 순열을 적어보고 규칙을 찾았다.

이 문제는 Factorial을 기반으로 하기 때문에, 각 인덱스는 (n-i-1)!로 나눴을 때 몫이 되는 값에 따라 숫자가 정해진다.

1~24번 째 까지는 맨 앞의 인덱스에는 1이 들어가고,

25 ~ 48번 째 까지는 2가 들어가고, 나머지도 이 방식과 같다.

즉 0번째 인덱스에는 4!로 나눈 몫이 들어간다는 말이다.

0	1	2	3	4
K를 (5-0-1)!로 나눈 값의 몫 (4! = 24로 나눈 값의 몫)	K를 (5-1-1)로 나눈 값의 몫 (3! = 6으로 나눈 값의 몫)	(K를 5-2-1)로 나눈 값의 몫 (2! =2 로 나눈 값의 몫)	K를 (5-3-1)로 나눈 값의 몫 (1! =1 로 나눈 값의 몫)	K를 (5-4-1)로 나눈 값의 몫 (0! =1 로 나눈 값의 몫)

 

하지만, 0번 째 인덱스에 k =24, k=48 과 같이 4!로 나누었을 때, 각각 0과 1이 되어야 하는데, 1과 2를 반환하기 때문에 답을 구해줄 수 없다. 그래서 입력받은 k값에서 1을 뺀 수를 가지고 문제를 풀어야 한다.

 

이제 각각 인덱스에 들어갈 숫자의 순서를 알게 되었다. 그럼 각각 인덱스에 알맞은 숫자를 넣어야할 차례인데, ArrayList를 통해 들어갈 수 있는 모든 값을 넣어주었다. (N이 20까지 밖에 안되기 때문에 배열로도 가능할 것 같지만, ArrayList가 더 효율적일 것 같다.)

 

위의 방식으로 진행하면서 K 또한 각각 인덱스에 맞게 줄여주어야 한다.

0번째 인덱스가 정해진 이후, 값을 채워 넣어야하는 n의 갯수는 4로 줄어들었기 때문에, 1번 째 인덱스는 (5-1-1)!로 나눈 값의 몫이 되는 것이다. 따라서, 각 로직마다 값을 처리한 후, K는 (5-n-1)!로 나눈 나머지 값을 저장해준다.

 

N= 5인 경우, ArrayList에는 1~5의 숫자가 0~4 인덱스에 들어가 있다.

입력받은 K= 5일 때, K=4로 변환하고 로직을 진행한다.

Idx : 0의 경우 (5-0-1)!로 나눈 값의 몫은 0이 된다.

Answer = {1, 0, 0, 0, 0},     남은 List = {2,3,4,5}  , K = K%(5-0-1)! ==> K%(24) = 4

 

Idx : 1의 경우 (5-1-1)!로 나눈 값의 몫은 0이 된다. ~> ArrayList의 0번째 값을 가져온다. => 2 (이후 리스트의 0번째 값 삭제)

Answer = {1, 2, 0, 0, 0},     남은 List = {3,4,5}   , K = K%(5-1-1)! ==> K%(6) = 4

 

Idx: 2의 경우 (5-2-1)!로 나눈 값의 몫은 2가 된다. ~>ArrayList의 2번째 값을 가져온다. => 5 (이후 리스트의 2번째 값 삭제)

Answer = {1, 2, 5, 0, 0},     남은 List = {3,4}   , K = K%(5-2-1)! ==> K %(2) = 0

 

Idx: 3의 경우 (5-3-1)!로 나눈 값의 몫은 0이 된다. ~>ArrayList의 0번째 값을 가져온다. => 5 (이후 리스트의 2번째 값 삭제)

Answer = {1, 2, 5, 3, 0},     남은 List = {4}   , K = K%(5-3-1)! ==> K %(1) = 0

 

Idx: 4의 경우 (5-4-1)!로 나눈 값의 목은 0이 된다. ~>ArrayList의 2번째 값을 가져온다. => 5 (이후 리스트의 2번째 값 삭제)

Answer = {1, 2, 5, 3, 4},     남은 List = {}   , K = K%(5-4-1)! ==> K %(1) = 0

 

이 로직만 이해한다면 쉽게 문제를 풀 수 있을 것이다.

 

코드

import java.util.ArrayList;

class Solution {
    public int[] solution(int n, long k) {
        int[] answer= new int[n];
        long[] factorials = getFactorials(n);
        ArrayList<Integer> numList = getNumList(n);
        k--;
        for(int i=0; i<n; i++) {
            int idx = (int) (k/factorials[i]);
            k %= factorials[i];
            answer[i] = numList.get(idx);
            numList.remove(idx);
        }
        return answer;
    }
    private long[] getFactorials(int n) {
        long[] result = new long[n];
        result[n-1] = 1;    // 마지막 idx => 0!
        
        for(int i = n-2; i>=0; i--) {
            result[i] = (n-i-1)*result[i+1];
        }
        
        return result;
    }
    
    private ArrayList<Integer> getNumList(int n) {
        ArrayList<Integer> result = new ArrayList<>();
        
        for(int i=1; i<=n; i++) {
            result.add(i);
        }
        return result;
    }
}