🤔| 프로그래머스 | LV.2 줄 서는 방법 - 구현 문풀 (Java)

⬛ 프로그래머스 | LV.2 줄 서는 방법 - 구현 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

진짜 이해하기도 어려웠다. 처음에 제한 사항에서 k 가 팩토리얼만큼 들어온다는 것을 못보고 단순히 DFS 탐색을 시도했는데 시간 초과가 뜨는… ㅠㅠ 효율적인 풀이를 찾아도 이해가 안돼서 오랫동안 보고 이해한 토대로 정리 했다.

https://void2017.tistory.com/136

[프로그래머스] 줄 서는 방법 (연습문제)

 

1차 시도 | 효율성 실패

DFS 로 풀었는데 효율성에서 실패가 떠서 보니 아차 싶었다…

k가 n이하로 봤는데 n! 이하였다… n이 최대 20이라서 20! 이면 엄청 큰 값이다. 그래서 long타입이었군.. ㅠㅠ

기존에는 카운팅을 해서 카운팅 개수가 k개와 같아질 때 answer를 세팅하고 있었는데, k가 매우 큰 값인 것을 알았기 떄문에 효율적으로 풀 방식을 찾아야 한다. ㅠㅠㅠ

import java.util.*;
class Solution {
    static int[] num;
    static boolean[] visited;
    static int[] lv_num;
    static int[] answer;
    static int cnt = 0;
    //DFS
    public static void DFS(int lv, int val, int n, long k){
        if(lv==n){
            cnt++;
            if(cnt == k) {
                for(int i=0; i<n; i++){
                    answer[i] = lv_num[i];
                }
            }
            return ;
        }
        
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                lv_num[lv] = num[i];
                DFS(lv+1, num[i], n, k);
                visited[i] = false;
            }   
        }
    }
    
    //솔루션 함수 
    public int[] solution(int n, long k) {
        answer = new int[n];

        num = new int[n];
        lv_num = new int[n];
        visited = new boolean[n];
        for(int i=1; i<=n; i++) num[i-1] = i;
        DFS(0, 0, n, k);
        
        return answer;
    }
}

---

2차 시도 풀이 | 흠.. 🤔..............................

1. 1~n까지의 수를 List에 담고, 동시에 모든 경우의 수 : n! 을 구한다.
2. while 을 i<n 인 동안 반복하면서 다음의 과정을 거치는데 설명하기 어려워서 풀어 쓴다. 

n! / (n-i) : 즉, 현재 구하려는 자리 제외 뒷자리의 경우의 수를 구한다.

예를 들어 n= 4 자리 추측할 거면 첫 번째 자리에는 4C1 올 수 있다. 그 뒷자리는 (24 / 4) = 6가지 숫자 조합이 올 수 있다. 그걸 미리 구해둔다. …

그리고 remain (태초에 k-1이던) / factorial 한 값의 몫으로 나온 value 가 (list = 1, 2, 3,4)에서 몇 번째 값인지 그 인덱스를 지칭해준다.

answer[i] 에는 list 상의 지칭한 값을 세팅 후 그 값은 사용했으니 list에서 remove 처리

remain은 이제 다시 factorial 만큼 나눠주고 다음 반복 처리

거의 이런 식의 흐름이고 그림으로 표현하면 다음과 같다. .. . 

(이해하기 어려웠는데 최대한 이해한 만큼 정리해뒀다. )

n = 4일 때 사전순 나열 그림

이 그림은 n = 4 (1, 2, 3, 4) 를 사전순으로 나열해서 k = 10번째인 숫자를 찾기 위해 그려놓은 그림이다.

그림 상에서 첫 번째 자릿수가 1일 때(4C1) 정했다 치고 보면 (고정), 그 뒤 세 자리에 올 수 있는 값의 경우의 수는 24/4 = 6가지 (갱신된 factorial)이다.

이걸 remain=k=10 이면 앞서 6가지보다 숫자가 큰상태이므로 첫 번째 자리가 1일 때는 불가능하다는 것을 알 수있다.

그래서 value = remain / 6 = 1 이 나오는데, 1, 2, 3, 4에서 인덱스가 1인 값 [2]가 첫 번째 자리가 된다.

그리고 이미 사용한 [2]를 List 상에서 제거시켜버리고 remain도 factorial 만큼 나눠서 갱신하고 다음 반복을 시도한다.

첫 자리 완성 후 뒷 자리 3개 자리에는 6가지 경우의 수 나

이런 식의 반복을 n의 자릿수만큼 하다보면 신기하게 2413 숫자 조합이 완성되기는 하는데 진짜 솔직히 말하면 이렇게 풀 자신은 없고 이해하기도 버겁다. ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 

💚 제출 코드

import java.util.*;

class Solution {
    //솔루션 함수 
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        List<Integer> list = new ArrayList<>();
        long factorial = 1;
        for (int i = 1; i <= n; i++) {
            list.add(i);
            factorial *= i;
        }
        // factorial : n! (n명 나열한 경우의 수)
        // list : 1 ~ n 까지 숫자 들어있는 리스트. answer 만들 때 숫자 하나씩 빼서 쓸 용도

        int i = 0; // answer 의 i 번째 자리 수 채워넣을 때 쓸 index
        long remain = k - 1;
        // k가 1부터 시작하므로
        while (i < n) {
            //i번째 자리 제외한 (뒤에 총 몇 가지 경우의 수 올 수 있냐 ) - 첫 번째에 4가 오면 그 뒷자리에는 6가지 
            factorial = factorial / (n - i); // 24 / 4 = 6 , 6 / 3 = 2,  2 / 2 = 1, 1/1 = 1 
            long value = remain / factorial; // 10 / 6 = 1 , 4 / 2 = 2, 0 / 1 = 0, 0/1 = 0
            answer[i++] = list.get((int)value); // 1번째 숫자는 2, 2 번째 숫자는 4, 3번째 숫자는 1 (0번쨰), 4번째 숫자는 3 (0번쨰)
            list.remove((int)value);
            remain = remain % factorial; // 10 % 6 = 4 , remain = 0 
        }

        return answer;
    }
}

ㅎㅎㅎ . . . 

근데 솔직히 아직까지도 먼말인지 잘 모르겠음