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

문제

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

코드

1. 시간 초과

class Solution {
    long k;
    long count = 0;
    int[] answer;
    boolean[] visited;
    int[] arr;
    
    public int[] solution(int n, long k) {
        this.k = k;
        arr = new int[n];
        visited = new boolean[n];
        func(0, n);
        return answer;
    }
    
    void func(int depth, int n) {
        // 이미 답이 있음을 의미
        if (answer != null) {
            return;
        }
        
        if (depth == n) {
            count++;
            
            if (k == count) {
                answer = arr.clone();
            }
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i + 1;
                func(depth + 1, n);
                visited[i] = false;
            }
        }
        
    }
    
}

단순히 완전 탐색을 이용하였으나, 시간초과가 났다.

2. 정답

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++) {
            factorial *= i;
            list.add(i);
        }
        
        k--;
        
        for (int i = n; i >= 1; i--) {
            factorial /= i;
            answer[n - i] = list.remove((int)(k / factorial));
            System.out.println(k + " " + factorial);
            k %= factorial;
        }
        
        return answer;
    }
}

거의 비슷하게 접근했었는데, 한 가지 간과한 점이 있었다. 반례를 찾으면서도 앞뒤가 안맞는다고 생각되는 요인 중 하나였다.

중간에 k-- 부분이었다.

k-- 을 해주는 이유?
인덱스는 0부터 시작하기 때문이다.


n = 4, k = 12인 경우를 생각해보자.
정수 1부터 4까지를 순서대로 정렬하여 나열했을 때, 12번째에 올 순서를 구하는 것이다.


만약 k를 12로 그대로 두고 첫 연산을 했을 때 12 / 6이 되고 (첫 factorial은 6이 된다.) [1, 2, 3, 4]에서 인덱스 상 두 번째 숫자인 3을 정답의 맨 처음 요소로 두게 되어 반례가 생긴다. k / factorial이 아직 정답에 배치되지 않은 원소들 중, 정답 원소로 배치될 인덱스 상 위치를 의미하게 되므로 맨 처음에 k--를 하고 시작해야 한다.