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

문제 링크

줄 서는 방법

풀이

• 처음에는 단순하게 순열 문제일 것이라고 생각했다. 그러나 정확성 테스트에서 시간과 메모리를 엄청 잡아먹으며 통과하더니 효율성에서 어그러졌다.
• 어떻게 풀어야하는지 날 모르겠어서 한참 고민하다가, 규칙성 문제라는 것을 다른 사람의 풀이를 보고 알았다.
• 다음과 같은 과정을 거치면서 배열을 완성하도록 한다.
  1. 배열의 인덱스는 0부터 시작하니, 일단 k--를 한다.
  2. 그리고 구할 수 있는 모든 배열의 순열의 수를 구한다.(n의 factorial)
  3. 이제 각 자릿수를 구해본다. 문제의 예시로 설명하면 n = 3, k = 5일 때, 전체 경우의 수는 3! => 6이다.
     여기서 규칙을 보면
     1,2,3
     1,3,2
     2,1,3
     2,3,1
     ..
     이렇게 2마다(전체 경우의 수/n) 숫자가 바뀜을 알 수 있다.
     그러므로, 6/3을 했을때 나오는 2를 통해서 우리는 [1,2,3]에서 2번째 인덱스에 해당되는 3이 첫번째 숫자로 와야하는 것을 알 수 있다.
     고로, n!를 n으로 나누면 ( = n-1!) 남은 숫자중에 몇번째 숫자가 들어와야하는지 알 수 있다.
     이러한 규칙을 바탕으로 n의 값을 하나씩 빼주고 위의 과정을 반복해서 배열의 인덱스의 자릿값을 구한다.
     

  import java.util.ArrayList;

  class Solution {
    public int[] solution(int n, long k){
        int[] answer = new int[n];

        ArrayList<Integer> people = new ArrayList<>();
        long factorial = 1;
        int index = 0;

        for(int i=1; i<=n; i++) {
            factorial *= i;
            people.add(i);
        }

        k--;
        while(n > 0) {
            factorial /= n;
            int value = (int) (k / factorial);
            answer[index++] = people.get(value);
            people.remove(value);

            k %= factorial;
            n--;
        }

        return answer;
    }
  }  
  
      // dfs 순열은 효율성에서 나가리
//    static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int r, long k) {
//        if (depth == r) {
//            cnt++;
//            if (cnt == k) {
//                result = output.clone();
//                return;
//            }
//        }
//
//        for (int i = 0; i < arr.length; i++) {
//            if (!visited[i]) {
//                visited[i] = true;
//                output[depth] = arr[i];
//                permutation(arr, output, visited, depth + 1, r, k);
//                visited[i] = false;
//            }
//        }
//    }

소감

• 규칙성 찾기에 매번 당하는 느낌이다.
• 아~이거 ~~문제구나 하고 풀었다가 어라? 하고 한참 머리쥐어뜯다가 풀이보고 아차싶다.
• 도대체 규칙성 찾는 사람들은 어떤 사람들일까...마냥 대단해보이는 요즘이다.