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

문제

---

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

프로그래머스

 

문제 분석

---

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

n 과 k 가 주어졌을 때 1 ~ n 까지의 숫자로 순열을 만들고 그 중 k 번째 순열이 무엇인 지 구하는 문제이다.

 

문제 접근

---

처음에는 간단한 순열 문제라 생각하고 k 번째 까지 가는 순열을 하나하나 구하면서 문제를 풀었다.

결과를 보니 효율성 테스트에서 전부 시간 초과로 실패하였다.

 

그래서 새롭게 접근했던 방법은 첫 번째 숫자는 미리 찾을 수 있다는 생각을 했다.

 

n = 4 [1 2 3 4] , k 20 이라고 가정한다면

 

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

=> 앞에가 1이 나오는 경우는 6개이다. 

 

마찬가지로 앞이 2가 나오는 경우도 6개, 3이 나오는 경우도 6개, 4가 나오는 경우도 6개로 총 24가지 경우의 수가 나온다.

 

그렇다면 20 / 6 = 3 ... 2 로 

 

제일 앞 숫자가 1, 2, 3 인 경우가 18개 이기 때문에 20번째 순열의 제일 앞에 나오는 숫자는 4가 될 것이다.

 

그럼 6이란 숫자는 어떻게 나올 수 있을까?

앞 숫자가 정해졌다면 숫자 3개로 순열을 만드는 방법의 개수와 같아진다.

앞이 1로 정해진다면 [2, 3, 4] 을 나열하는 방법의 수이다. 즉 3! 이다.

 

맨 앞의 숫자가 정해졌다면 2번째 숫자도 똑같은 방법으로 정할 수 있다.

 

위의 예시를 계속 사용하면

[4] 까지는 정해졌고, [1, 2, 3] 중에 2 번째 (아까 나온 나머지) 순열을 구하는 문제로 변경된다.

 

같은 방법으로 

2 / 2! = 1 ... 0 이지만 문제를 풀기 위해 0 ... 2 로 변경한다.

 

그럼 [4, 1] 까지 정해지고 [2, 3] 중에서 2 번째 순열을 구하는 문제로 변경된다.

 

2 / 1! = 2 ... 0 -> 1 ... 2 

[4, 1, 3] , [2]

 

=> 정답 [4, 1, 3, 2] 

 

주의!

분명히 최적화해서 문제를 풀었다고 생각했음에도 효율성 테스트는 시간 초과가 났다...

자바 스트림을 사용해서 리스트를 배열 형태로 변경했었는데 이 부분이 시간 초과의 원인이었다. 

코드

---

import java.util.*;

class Solution {
    static long[] memo = new long[21];
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        List<Integer> list = new ArrayList<>();
        List<Integer> nums = new ArrayList<>();
        memo[1] = 1;
        memo[2] = 2;
        
        for(int i=1; i<=n; i++){
            nums.add(i);
        }
        
        while(n > 1){
            long fac = factorial(--n);
            int idx = (int)(k / fac);
            k = k % fac;
            
            if(k==0){
                idx-=1;
                k = fac;
            }
            
            list.add(nums.get(idx));
            nums.remove(idx);
        }
        list.add(nums.get(0));
        
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
    
    public long factorial(int num){
        if(memo[num] != 0){
            return memo[num];
        }
        
        memo[num] = num * factorial(num-1);
        return memo[num];
    }
}