[프로그래머스 level_3] 줄 서는 방법 for JAVA

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

프로그래머스

[문제 설명]

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

---

입출력 예

n	k	result
3	5	[3,1,2]

 

[풀이]

순열을 구하고 순서에 맞는 배열을 반환하는 알고리즘을 구현하기에는 숫자가 너무 커서 안될 가능성이 높다.

그래서 우리는 정해진 자리에 맞는 숫자들을 추측해야 한다.

글씨를 못써도 너무 못쓴다.

 

위와 같은 방식을 n = 0이 아닐 때 까지 구해주면 된다. '

 

[코드]

public int[] solution(int n, long k) {
        ArrayList<Integer> al = new ArrayList<>();
        int[] result = new int[n];
        int fn = 1;
        for(int i = 1;  i <= n; i++) {
            fn *= i;
            al.add(i);
        }
        k--;
        
        int idx = 0;
        while(n>0) {
            fn /= n;            //n번 째 자리수가 정해짐
            result[idx++] = al.get((int) (k/fn));
            al.remove((int)k/fn);
            k %= fn;
            n--;
        }
        return result;
        
    }

 

느낀 점 : 처음에 너무 어려워서 다른 사람이 푼 방식을 참고해서 공부했다. 이해하려고 2시간 쯤 소비했다. 다음날이 되니 개념이 굳어져서 이해가 확실히 됐다.