줄서는 방법 : https://school.programmers.co.kr/learn/courses/30/lessons/12936#
Problem
Solve
문제를 처음보고 완탐으로 Set에 줄 서는 방법을 넣고 정렬해서 가져올까 라는 생각을 했었습니다.
하지만 제한사항의 k가 최대 20!인것을 보고 다른 방법을 생각해내야했었습니다.
그래도.. 호오옥시나 하는 마음에 구현은 해보았지만 당연히 시간초과가 발생하였고 k위치의 값을 직접적으로 찾을수 없을까하는 접근 방법을 사용해보기로 했습니다.
예를들어 n = 4, k = 15인 값을 찾고자한다고 가정해보겠습니다.
경우의 수를 모두 나열해보고 15번째의 값은 [3,2,1,4] 인 3번째 블럭의 3번째 줄에 존재합니다.
총 경우의 수 = n! , 한 블럭의 개수 = 총 경우의수 / n , k의 위치 = k/블럭의 개수 로 구할 수 있게됩니다.
이때, 인덱스로 값을 구할 것이기 때문에 k에서 1를 하나 빼주고 시작해주어야합니다.
그렇다면 첫번째 1,2,3,4 에서 k=14 (15에서 1빼줌)를 아래와 같이 구해줍니다.
(1)
그렇게 되면 2번째 블럭에 있는 첫번째 값인 3을 골라주고, 나머지 수인 1,2,4 중 다시 값을 선택하기 위해 위와 같은 과정을 거쳐야하기 때문에 k를 갱신해주어야합니다.
다음 k값 = 기존 k값 % 한 블럭의 개수 을 통해 구할 수 있습니다. 그렇기에 첫번째 과정에서는 다음 k값 = 14 % 6 = 2가 됩니다.
2
나머지 n = 3, k = 2 인 1,2,4 를 구하면 총 개수 = 6, 블럭의 개수 = 2, k의 위치 = 1 이게 되고 1번째 인덱스에 있는 첫번째 수인 2를 구해줍니다.
그리고 다음 k값 = 2 % 2 = 0 이 됩니다.
3
1을 가지게 됩니다.
4
4를 가지게 됩니다.
이러한 과정을 거치게 되면 [3,2,1,4]의 값을 얻을 수 있게 됩니다.
이때 저는 List를 이용하여 인덱스를 사용해 k번째 위치의 사람을 찾아서 제거하는 식으로 List의 크기가 0이 될때까지 반복하였습니다.
자세한건 코드에서 확인해보겠습니다.
Code
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
class Solution {
public int[] solution(int n, long k) {
List<Integer> list = new ArrayList<>();
long total = 1; //해당 n의 총 경우의 수(팩토리얼)
for(int i=1;i<=n;i++){
list.add(i);
total *= i;
}
int[] answer = new int[n];
int idx = 0;
k--; //index활용을 위해 k에서 1를 빼고 시작
while(list.size() != 0){ //모든 사람을 선택할때까지 반복
long block = getBlock(total, list.size()); //한 블럭의 개수
int index = getIndex(k, block); //k의 위치
total /= list.size(); //다음 n에 대한 경우의 수
answer[idx++] = list.remove(index); //해당 k의 위치에 있는 사람을 list에서 제거하고 answer에 저장해준다.
k = nextK(k,block); //다음 k
}
return answer;
}
public long getBlock(long total, int range){
return total/range;
}
public int getIndex(long k, long block){
return (int)(k/block);
}
public long nextK(long k, long block){
return k%block;
}
}Result
처음에는 삭제가 자주 발생하고 List에 재정렬로 인해서 List가 아닌 LinkedList를 사용했는데 적게는 5배, 많게는 10배의 시간 차이가 나서 List를 사용했습니다. 아무래도 remove에서 index탐색으로 인해 index의 영향을 많이 받아서 그런것 같습니다.
Reference
