문제 설명
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문제의 예시와 같습니다.
나의 풀이
import java.util.*;
class Solution {
public int[] solution(int n, long k) {
int[] answer = new int[n];
int answerIdx = 0;
List<Integer> list = new ArrayList<>();
list.add(-1);
for (int i = 1; i <= n; i++) {
list.add(i);
}
while (n > 1) {
Long indexLong = (k - 1) / fact(n - 1) + 1;
int index = indexLong.intValue();
answer[answerIdx++] = list.get(index);
list.remove(index);
k = k - (indexLong - 1) * fact(n - 1);
n--;
}
answer[answerIdx] = list.get(1);
return answer;
}
long fact(int n) {
if (n == 1) {
return 1L;
}
return n * fact(n - 1);
}
}
Java
복사
Remark
•
풀이 아이디어
◦
[프로그래머스/Java] 124 나라의 숫자 (lv.2) 문제처럼 나누기를 통해 그룹을 묶어 풀이함▪
나누기를 통해 그룹을 묶는 것은 게시판 페이징 할 때도 쓰는 개념
◦
예를 들어 n = 2일 때 [1, 2]와 [2, 1] 케이스가 있음
◦
n = 3이라면 1, 2, 3이 맨 앞에 오는 경우의마다 n = 2일 때의 케이스가 붙음
1 1 2
1 2 1
2 1 2
2 2 1
3 1 2
3 2 1
Java
복사
◦
즉, n은 (n - 1)! 개를 하나로 묶은 그룹 n개를 가지고 있고, 맨 앞의 수가 그룹의 번호가 됨
1 | 1 1 2
2 | 1 2 1
3 | 2 1 2
4 | 2 2 1
5 | 3 1 2 <-- k == 5
6 | 3 2 1
Java
복사
◦
따라서 (k - 1) / (그룹 크기) + 1을 하면 맨 앞의 수(그룹의 번호)를 알 수 있기 때문에 answer에 해당 그룹 번호를 넣고 리스트에서 지움. 위의 경우는 (5 - 1) / 2 + 1 = 3
1 | 1 2 <-- k == 1
2 | 2 1
Java
복사
◦
리스트에는 1과 2만 남고, k의 그룹에서의 상대적인 크기를 알기 위해 앞의 두 그룹 크기 합(4)을 k에서 빼줌
▪
그룹 크기 합은 (k의 그룹 번호 - 1) * (그룹 크기)
◦
k는 1이 되고, 위와 같은 과정을 반복함
◦
리스트에 숫자가 하나만 남으면 해당 수를 마저 정답에 넣고 return
•
특별히 느린 로직은 아닌 것 같은데 계속 돌려도 효율성 2번이 시간 초과가 남
◦
될 때까지 무한 제출하는 떼쓰기 전략을 사용
◦
8번 쯤 돌리니 성공함