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

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

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

class Solution {
	    public int[] solution(int n, long k) {
	        int[] answer = new int[n];
	        boolean[] check = new boolean[n+1];
	        long[] factorial = new long[n];
	        
	        
	        calFactorial(factorial,n);
	        solve(factorial,answer,check,n,n-1,k-1,1);
	    
	        return answer;
	    }

		private void calFactorial(long[] factorial, int n) {
			factorial[0]=1;
			for(int i=1; i<n; i++) {
				factorial[i]=factorial[i-1]*i;
			}
			
		}

		private void solve(long[] factorial, int[] answer,boolean[] check, int len, int n, long k, int idx) {
			//우선 현재  k / n - idx! 을 구해서
			if(n==-1) return;
			long result = k / factorial[n]; //
			answer[idx-1]=selectNum(result,check,len);
			solve(factorial, answer, check, len, n-1, k%factorial[n], idx+1);
		}

		private int selectNum(long result, boolean[] check, int len) {
			for(int i=1; i<=len; i++) {
				if(!check[i]) {
					if(--result==-1) {
						check[i]=true;
						return i;
					}
				}
			}
			return 0;
		}
	}

소요시간 : 1시간

 

n개의 숫자로 만들어진 순열 중 k 번째 순열을 찾는 문제입니다

n의 조건이 최대 20이니까 당연히 순열은 안 돌아가겠죠? 20! 이면 구해보진 않았지만 어마어마 어마 하게 큰 수입니다.

 

즉 수식을 통해 k번째의 순열을 뽑아야 된다는 말입니다!

 

예를 들어 봅시다.

 

현재 위의 순열을 살펴보면 맨앞자리 기준으로 2개, 2개, 2개가 나뉘어있습니다!

맨 앞차를 고정해놓고 뒤의 두 자리를 구하는 경우의 수는 2! =  2입니다.

 

즉 첫 번째 자리를 고정시켜놓고 뒷자리를 구하는 방법은 ( n-1)!입니다.

만약 n이 3k가 4라고 해봅시다. 즉 [2, 3, 1]이라는 순열을 뽑아야 합니다.

 

그럼 첫 번째 자리를 구해봅시다.

 

(k-1)/ (n-1)! = 3 / 2 = 1.xxx  즉, 첫번째 자리는 한번 변했다,-> 순열이 한번 돌았다 -> 2다 라는 결론이 나옵니다.

 

그럼 두 번째 자리를 구해봅시다. 두번째에서 k는 첫번째식에서 (k-1) % (n-1)! 을 사용합니다.

(k-1)/ (n-2)! = 1 / 1 = 1  즉, 두번째 자리는 한번 변했다. -> 순열이 한번 돌았다 -> 3이다.(2는 이미 사용 1에서 바로 3)

 

그럼 세 번째 자리를 구해봅시다. 세번째에서 k는 두번째식의 (k-1) % (n-1)!을 사용합니다.

(k-1)/ (n-3)! = 0 / 0 = 0 즉, 세번째 자리는 변하지 않았다. -> 현재 남아있는 수를 넣어주면 끝

 

이런 로직을 통해 dfs를 구현하였습니다.

이 글을 보고 한번 손으로 작성해보시면 감이 오실 겁니다.. 저는 a4용지 1장 앞뒤로 빼곡히 써서 이해했습니다..

 

끝~