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

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

프로그래머스

코딩테스트 연습 > 연습문제 > 줄 서는 방법

 

난이도: LEVEL2

알고리즘 유형: 구현

 

문제 풀이 

n명의 사람이 줄을 서는데 사람을 나열하는 방법을 사전 순서대로 나열했을 때 K번째 방법을 반환해라 

 

EX) 3명의 사람 → 6가지 방법 

[1, 2, 3] : 1
[1, 3, 2] : 2
[2, 1, 3] : 3
[2, 3, 1] : 4
[3, 1, 2] : 5 
[3, 2, 1] : 6

 

n명의 사람을 나열하는 방법은 n!이다.

만약 k가 5라면 [3, 1, 2]를 반환한다. 

 

N은 최대 20이어서 완전 탐색으로 구하면 시간 복잡도가 O(N!) 이어서 통과 못한다. 

그럼 어떻게 풀어야 할까?

 

나는 경우의 수 범위를 통해서 하나씩 찾아가는 방식으로 구현 하였다. 

정답 코드 

import java.util.*;
class Solution {
    static long [] count;
    static int [] memo;
    static boolean [] visited;
    static int N; static long K;
    public int[] solution(int n, long k) {
        N = n; K = k;
        init();
        find(0, 1);
        return memo;
    }
    public static void find(int depth, long cur){
        if(depth == N - 1){
           for(int i = 1; i <= N; i++){
               if(!visited[i]){
                   memo[depth] = i;
                   break;
               }
           } 
           return;  
        } 
        long temp = count[N - depth - 1] / (N - depth);
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 1; i <= N; i++){
            if(visited[i]) continue;
            list.add(i);
        }
        for(int i = 0; i < N - depth; i++){
            if(cur + (temp * i) <= K && K < cur + (temp * (i+1))){
                visited[list.get(i)] = true;
                memo[depth] = list.get(i);
                find(depth + 1, cur + (temp * i));
                return;
            }    
        }    
    }
    public static void init() {
        visited = new boolean [N+1];
        memo = new int [N];
        count = new long[N];
        long cnt = 1;  
        for(int i = 1; i <= N; i++){
            cnt *= i;
            count[i-1] = cnt;
        }
    }
}