줄 서는 방법(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

n명의 사람을 n!(factorial)만큼 가지수로 나열했을 경우 k번째 나열 순서 리턴

 

---

 

풀이

 

접근 방식

1. 각 인덱스의 숫자가 얼마의 반복 주기를 갖는지 확인

  → n = 4의 경우 {1, 2, 3, 4} / {1, 2, 4, 3} / {1, 3, 2, 4} / {1, 3, 4, 2} / {1, 4, 2, 3} / {1, 4, 3, 2} / {2, 1, 3, 4} / ...

  → 첫 번째 숫자의 경우 6개, 두 번째 숫자의 경우 2개, 세 번째와 네 번째는 각각 1개의 반복 사이클을 갖는다.

  → n = 4의 경우 반복되는 사이클을을 배열로 나타내면 {(n-1)!, (n-2)!, (n-3)!, (n-4)!} 임을 확인 할 수 있다.

 

2. k를 통해 각 인덱스에 해당하는 숫자 구하기

  → k = 5인 경우, k-1을 반복 사이클 배열의 각 인덱스로 나눈 몫이 해당 자리의 숫자가 된다.

  → 이때 k %= (반복 사이클)

 

---

 

코드리뷰

 

import java.util.*;

class Solution {
    int n;	// n = 4
    long k, K;	// k = 5, K = k - 1 = 4 (1을 빼는 이유는 첫 번째 인덱스의 숫자는 6개를 반복 주기로 갖는데 6번째 숫자의 경우 몫이 1이 되기 때문)
    List<Integer> list = new ArrayList<>();	// list = {1, 2, 3, 4}
    List<Integer> answerList = new ArrayList<>();
    List<Long> termList = new ArrayList<>();	//	termList = {6, 2, 1, 1}
    
    public void dfs(List<Integer> list) {
        if(list.isEmpty()) {
            return;
        }
        long term = termList.remove(0);	// (n-1)! = 6
        long quot = K / term;	// 4 나누기 6 의 몫 = 0
        answerList.add(list.remove((int)quot));	// {1, 2, 3, 4}에서 index = 0번째 숫자(=1) 제거
        K %= term;	// 4 나누기 6 의 나머지 = 2
        dfs(list);	// {2, 3, 4}를 dfs의 인자로 넘김
    }
    
    // 팩토리얼 구하기
    public long factorial(long N) {
        long result = 1;
        if(N == 1 || N == 0) {
            return result;
        } else {
            for(long i = 1; i <= N; i++) {
                result *= i;
            }
            return result;
        }
    }

    public int[] solution(int n, long k) {
        this.n = n;
        this.k = k;
        K = k -1;

        for(int i = 0; i < n; i++) {
            list.add(i+1);
        }
        for(long i = n-1; i >= 0; i--) {	// n-1부터 팩토리얼 구하기
            termList.add(factorial(i));
        }
        dfs(list);
       return answerList.stream().mapToInt(i -> i).toArray();
    }
}