[프로그래머스/Level3] 줄 서는 방법 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

1. 첫 번째 숫자는 n! / n번 나온다. ▷ 첫 번째 숫자로 시작하는 숫자 조합의 수 = (n - 1)!

(예를 들어 n이 3, k가 5일 때, 앞이 1로 시작하는 숫자는 3!/3 = 2! = 2번 나온다. → [1,2,3], [1,3,2])

 

2. 첫 번째 자리가 구해지면, 대기 중인 사람을 리스트에서 제거하고, 정답 배열에 숫자 삽입한다.

▷ (구할 번호 k / 앞에서 구한 단위 fac)

 

3. 다음 자리를 구하기 위해, 구할 번호 k는 단위만큼 제거한다.

 

 

핵심은 모든 순열을 구하려고 하는 거이 아니라,

특정 위치의 순열 하나만 구하는 방식으로 해결하는 것이다! (참고)

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        
        List<Integer> list = new ArrayList<>(); // 사람 리스트
        long fac = 1;   // 팩토리얼
        
        for(int i = 1 ; i <= n ; i++) {
            list.add(i);
            fac *= i;
        }
        
        k--;    // 인덱스 맞추기용
        int idx = 0;
        
        while(idx < n) {
            fac /= (n - idx); // (단위) 숫자가 나오는 경우의 수 : (n!/n)번
            answer[idx++] = list.remove((int)(k / fac));    // (구할 번호 / 단위) 첫 번째 자리가 구해지면, 대기 중인 사람을 리스트에서 제거하고, 정답 배열에 숫자 삽입
            k %= fac;   // 다음 자리 구하기 위해 구할 번호 k는 단위만큼 제거
        }
        
        return answer;
    }
}

 

 

---

💦 어려웠던 점

- n이 20 이하이기 때문에 재귀로 했다간 시간초과가 난다... (는 내 얘기)

 

틀린 코드 확인하기

import java.util.*;
 
class Solution {
    static int n;
    static boolean[] visited;
    static List<Integer> tmpList = new ArrayList<>();
    static List<String> list = new ArrayList<>();    
    
    public int[] solution(int n, long k) {
        this.n = n;
        
        visited = new boolean[n + 1];                
        permutation(0);
        
        String[] str = list.get((int)k - 1).split(" ");
        
        int[] answer = new int[n];
        for(int i = 0 ; i < n ; i++) {
            answer[i] = Integer.parseInt(str[i]);
        }        
        return answer;
    }
    
    private static void permutation(int depth) {
        if(depth == n) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0 ; i < tmpList.size() ; i++) {
                sb.append(tmpList.get(i) + " ");
            }
            list.add(sb.toString());
            return;
        }
        
        for(int i = 1 ; i <= n ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                tmpList.add(i);
                permutation(depth + 1);
                visited[i] = false;
                tmpList.remove(tmpList.size() - 1);
            }
        }
    }
}

 

 

🧐 새로 알게 된 내용

 사실 문제를 100% 이해하지 못 했다..

복습을 해야겠다,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

프로그래머스 - 줄 서는 방법 JAVA :: 12936

프로그래머스 순열 — 줄 서는 방법(JAVA)

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

(Java) 프로그래머스 줄 서는 방법

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