[줄 서는 방법] 코딩테스트 연습 > 연습문제 > 줄 서는 방법
틱톡라이트 초대링크 https://lite.tiktok.com/t/ZSjqX7SfC/
[기간 한정] 보는 재미로, 버는 재미로! 영상만 봐도, 좋아요만 눌러도, 검색만 해도, 포인트가 차
www.tiktok.com
※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※
[문제설명]
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! 이하의 자연수 입니다.
입출력 예
입출력 예시 설명
입출력 예 #1
문제의 예시와 같습니다.
[간단설명]
n명의 줄서는 방법 중에서, K번째 경우의 수 구하기
[접근방법]
1. n!(팩토리얼) 을 구한다.(fac)
2. 나누어줄 분모를 구한다.(demo)
3. 리스트에 사람을 1~n까지 집어넣는다.
4. k를 계산하기 쉽게 -1해준다.
ex) 5-1 = 4
5. 사이클을 구한다. (fac/demo 한 경우가 1사이클이다.)
ex) 즉, n!=6, demo=3 -> 2가 1사이클이 된다.
6. k를 사이클로 나눈 몫(mok) 을 구한다.
ex) k=4, 사이클=2, k/2 = 2
7. k를 사이클로 나눈 나머지로 갱신한다.
ex) k=4, 사이클=2, k%2 = 0
8. 리스트에서 mok에 해당하는 차례의 사람을 지운다.
ex) mok=2 이면, 3번째 사람
9. 정답에 해당 사람을 추가한다.
[주의사항]
- 이 문제는 모든 경우의수를 배열로 만들고, k를 찾으려고 하면 시간초과로 풀 수가 없다.
- 첫 번째 사람을 구하고, 두 번째 사람을 구하고,, 이런식으로 수식을 세워서 풀어야한다.
- k가 long 타입이므로, 다른 변수 선언 및 계산시에도 long 타입을 맞춰줘야 한다.(런타임 오류)
[소스공개]
import java.util.*;
class Solution {
public int[] solution(int n, long k) {
// n! 구하기
long fac = fac(n,1);
// 분모 구하기
long deno = 1;
// 리스트에 n명을 집어넣는다.
List<Integer> list = new ArrayList<>();
for(int i=0;i<n;i++){
list.add(i+1);
}
// 정답배열
int[] answer = new int[n];
// 정답배열의 인덱스
int idx=0;
// 몫과 나머지를 계산하기 위해, k-1을 해준다.
k=k-1;
// k번째 나열 구하기
for(int i=n;i>0;i--){
// 분모를 계속 곱해준다.
deno *= i;
// 현재 차례에서의 경우의 수
// (n! 나누기 분모)
long num = fac/deno;
// 현재 몫
// k번째 나누기 경우의 수
long mok = k/num;
// k는 나누기를 했으니, 나머지로 바꿔준다
k = k%num;
// 현재 차례에서의 사람 찾아서 지우기
int now = list.remove((int)mok);
// 정답 배열
answer[idx++]=now;
}
// 정답 리턴
return answer;
}
// 팩토리얼 만들기
public long fac(int n, long sum){
if(n>1){
return fac(n-1,sum*n);
}else{
return sum;
}
}
}
[실행결과]
