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

문제 설명

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]

---

 

입출력 예 설명

 

입출력 예 #1
문제의 예시와 같습니다.

---

풀이

 

---

사용 변수

	List<Integer> list = new ArrayList<>(); 	//-> 선택 가능 숫자 배열
        long factorial = 1;				//-> 팩토리얼  
        int []answer = new int[n]; 			//-> 정답 배열
        int idx = 0; 					//-> 반복문 인덱스

설명

이 문제는 굉장히 고전한 문제였습니다. 정답률 낮은 데에는 이유가 있구나.. 싶은 문제였고, 풀이를 떠올리는데 굉장히 오래 걸렸습니다.

입력에는 숫자 n 과 찾아야 할 수 k 가 주어집니다. 처음 구현할 때에는 백트래킹 문제인가? 싶었습니다. N 과 M 시리즈 처럼 가능한 모든 숫자 열을 중복 없이 출력 한 후, k 번까지만 탐색하면 되지 않을까? 싶었지만, 제한 사항과 효율성 테스트를 보니 분명 시간 초과가 날 상황 이었습니다.

 따라서 다른 어떠한 방법을 이용하여 풀어야 하는데, 그 방법이 잘 생각나지 않았습니다. 고민 끝에 얼추 떠오른 방법은, 나눗셈을 이용하여 첫 자리를 판별하자,, 정도였습니다. 

일단 배열은 0부터 시작하기 때문에 구하는 값 k -=1 상태로 진행합니다. 

한숨 나오는 제 필기체..

n이 4고, 구하는 수 k 가 9라고 가정합니다. (k-=1) == 8 입니다. 총 4! 인 24개의 요소들이 나올 수 있는데,

앞자리로 구분한다고 하면 0, 1, 2, 3, 4칸으로 구분이 가능합니다. 각 칸 당 6개의 값들을 가지고 있습니다. 

24개에서 요소 개수로 나누면, 6, 각 요소가 가지고 있는 값의 양이 나옵니다. 

우리가 구하고자 하는 값 k 는 8이고, 8 / 6 1.xx 입니다. [1, 2, 3, 4] 배열 중에서 1번 째 값인 2가 첫번째 값이 됩니다.

k 를 이용해 구했으므로, k 값을 갱신합니다. k(구하는 값) % 요소 값(6) = 2 입니다. 

 

2번째 수를 구하는 경우입니다. 똑같이 구해보겠습니다.

값 개수 = 6, 요소 개수 = 3;  6/3 =2 

(k)2 / 2 = 1; [1, 3, 4] 입니다. 

 

이런 식으로 구해주면 되겠습니다. 

 

 

 

 

 

 

소스코드

 

package prgmrs;

import java.util.*;

public class 줄서는방법 {

    public static void main(String[] args) {
        int n = 4;
        int k = 8;
        solution(n,k);

    }
    public static int[] solution(int n , int k ){
        List<Integer> list = new ArrayList<>();
        long factorial = 1;
        int []arr= new int[n];
        int []answer = new int[n];
        for (int i = 0; i <n ; i++) {
            list.add(i+1);
            factorial*=i+1;
        }
        k -=1;
        int idx = 0;
        while(idx < n){
             factorial = factorial / (n - idx);
             answer[idx++] = list.remove((int)(k/factorial));
             k %= factorial;
        }
        return answer;
    }

}

 

---

느낀 점

이번 문제는 너무 어려웠습니다. !  학기가 시작했지만 알고리즘도 놓지 말고 해야겠습니다.