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

얼마 전까지 Lv3에 있었던 문제였는데 얼마 전에 Lv2로 내려왔다.

다른 Lv2는 기본적인 알고리즘을 구현할 수 있다면 바로 풀리는 문제들이었는데

이 문제는 알고리즘 + 응용이 필요하다고 느꼈다.

그래서 많이 어려웠고 Lv2 보다는 Lv3에 가까운 문제가 아닐까 생각이 든다.

 

처음에는 가능한 모든 순열을 전부 구하고 이를 리스트에 저장해

k번째 항목을 출력할 생각이었다.

그러나 메모리 초과, 시간 초과 등으로 성공하지 못했고 조건에 n이 20 이하의 자연수라는 것을 보고

최대 20! 개의 순열이 나오는 걸 고려하지 않았다는 사실을 깨달았다.

 

다른 방법이 도저히 떠오르지 않아 검색을 하여 다른 분들의 정답을 참고했다.

k를 이용해서 각 자리에 들어갈 수를 구해야 한다는 걸 알게 되었지만 로직을 이해하기 어려웠다.

코드는 복잡하지 않지만 팩토리얼에 대해 생각을 많이 해봐야 조금씩 이해가 간다.

나중에 다시 풀어볼 예정이다.

 

실패 코드(순열 이용 - 메모리 초과, 시간 초과)

import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    public int[] solution(int n, long k) {
        int[] arr = new int[n];
        int[] out = new int[n];
        boolean[] visited = new boolean[n];
        list = new ArrayList<>();

        for(int i=0; i<n; i++) {
            arr[i] = i+1;
        }

        perm(arr, out, visited, 0, n);

        int[] answer = list.get((int) (k-1));
        
        return answer;
    }
    static void perm(int[] arr, int[] out, boolean[] visited, int depth, int n) {
        if(depth == n) {
            list.add(out.clone());
            return;
        }
        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                out[depth] = arr[i];
                perm(arr, out, visited, depth + 1, n);
                visited[i] = false;
            }
        }
    }
}

 

최종 코드

import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];

        ArrayList<Integer> list = new ArrayList<>();
        long factorial = 1;
        int idx = 0;

        // 팩토리얼과 사람 리스트 구하기
        for (int i = 1; i <= n; i++) {
            factorial *= i;
            list.add(i);
        }

        // 인덱스를 맞추기 위해 k--
        k--;

        while (n > 0) {
            // 각 자리에 자리에 들어갈 경우의 수
            factorial /= n;
            // 자리 숫자 결정
            int val = (int) (k / factorial);
            // 정답 배열에 숫자 삽입
            answer[idx] = list.get(val);
            list.remove(val);
            
            // 다음 자리수를 구하기 위해 k값 변경
            k %= factorial;
            idx++;
            n--;
        }
        return answer;
    }
}