Programmers | Level 2 | 줄 서는 방법
Programmers | Level 2 | 줄 서는 방법
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Math
Description
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 함수를 완성해주세요.
Constraints
n은 20이하의 자연수 입니다.k는 n! 이하의 자연수 입니다.
Examples
| n | k | result |
|---|---|---|
| 3 | 5 | [3, 1, 2] |
Solutions
Code
import java.util.*;
class Solution {
public int[] solution(int n, long k) {
// 1부터 n까지의 숫자를 저장할 리스트
List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= n; i++) {
numbers.add(i); // 후보 리스트에 숫자 추가
}
k--; // k 값을 0-based로 맞추기 위해 1 감소
int[] result = new int[n]; // 결과를 저장할 배열
for (int i = 0; i < n; i++) {
long factorial = factorial(n - i - 1); // 남은 자리 수에 대한 팩토리얼 계산
int index = (int)(k / factorial); // k를 팩토리얼로 나눈 몫이 현재 자리에 올 숫자의 인덱스
result[i] = numbers.remove(index); // 인덱스에 해당하는 숫자를 결과 배열에 추가하고, 후보 리스트에서 제거
k %= factorial; // 나머지를 통해 k 값을 갱신
}
return result; // 최종 k번째 순열을 반환
}
// 팩토리얼을 계산하는 함수
private long factorial(int n) {
if (n == 0) return 1; // 0!은 1로 처리
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i; // 팩토리얼 계산
}
return result; // 계산된 팩토리얼 값 반환
}
}
Approaches
이 문제는 수학적 개념인 순열과 팩토리얼을 기반으로 특정 순열을 찾는 문제입니다. n명의 사람이 줄을 서는 방법은 총 n!개의 경우의 수가 존재하며, 이를 사전 순으로 정렬했을 때 k번째 순열을 찾아야 합니다. 각 자리에서 가능한 선택지를 팩토리얼을 이용해 계산하고, 그에 맞는 순서를 효율적으로 찾아가는 방식으로 문제를 해결합니다.
1. 문제 분석
주어진 문제에서 n명의 사람이 일렬로 줄을 서는 경우의 수는 n!입니다. k번째 순열을 구하기 위해서는 각 자리에서 가능한 선택지를 계산해야 합니다. 예를 들어, 첫 번째 자리에 n명이 올 수 있으므로 각 자리에 배치할 수 있는 방법은 n-1!로 계산됩니다. 이를 통해 k번째 순열을 효율적으로 찾을 수 있습니다.
k번째 순열을 찾는 방법은 각 자리에 놓일 수 있는 값을 팩토리얼 계산을 통해 구분하는 것입니다. 먼저 n명의 후보 리스트를 생성한 후, k번째에 해당하는 사람을 한 명씩 선택해 나가는 방식으로 접근합니다. 이를 반복하면서 마지막까지 순열을 완성합니다.
2. 접근 방식
k번째 순열을 찾기 위해 수학적 개념인 팩토리얼을 활용하여 각 자리에 올 숫자를 효율적으로 결정하는 방법을 사용합니다.
- 팩토리얼 계산 및 초기화: n명의 사람이 줄을 서는 모든 경우의 수는 n!입니다. 각 자리에서 선택할 수 있는 후보의 수는 남은 사람 수의 팩토리얼로 계산할 수 있습니다. 예를 들어, 첫 번째 자리에 올 수 있는 후보의 수는 (n-1)!이며, 이를 통해 k번째 순열에서 각 자리에 어떤 숫자가 올지를 효율적으로 계산합니다. 팩토리얼을 계산하는 함수를 사용해 각 자리에서 가능한 후보군을 좁혀나갑니다.
- k 값 조정: 문제에서 주어지는 k는 1-based(1부터 시작) 숫자이므로, 이를 0-based(0부터 시작) 값으로 맞추기 위해 k 값을 1 감소시킵니다. 이렇게 조정된 k 값을 사용해 나머지 자리의 숫자를 선택할 때 사용할 수 있습니다.
- 순열 구하기: 각 자리마다 팩토리얼 값을 이용해 선택할 후보를 정합니다. 팩토리얼을 통해 현재 자리에 올 수 있는 후보의 인덱스를 계산하고, 해당 숫자를 선택한 후 후보 리스트에서 제거합니다. 이렇게 계산을 반복하면서 나머지 숫자들로 다음 자리를 채워가며 최종적인 k번째 순열을 구합니다.
3. 팩토리얼을 사용한 k번째 순열 계산
n명의 사람들이 줄을 설 수 있는 경우의 수는 n!입니다. k번째 순열을 찾기 위해서는 각 자리에서 가능한 숫자의 개수를 효율적으로 계산해야 합니다. 각 자리에 올 수 있는 숫자의 개수는 남은 사람의 팩토리얼 값을 사용하여 계산할 수 있습니다. 예를 들어, 첫 번째 자리에 올 수 있는 사람은 (n-1)!개의 선택지를 갖습니다. 팩토리얼을 계산하기 위한 함수를 작성해, 이를 통해 각 자리의 숫자를 결정할 준비를 합니다.
팩토리얼을 계산하는 함수는 n이 0일 때 1을 반환하고, 1부터 n까지의 곱을 계산해 반환합니다.
private long factorial(int n) {
if (n == 0) return 1; // 0!은 1
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i; // 팩토리얼 계산
}
return result;
}
4. 후보 리스트 생성 및 초기화
순열을 만들기 위해서는 1부터 n까지의 숫자를 후보로 가진 리스트를 생성해야 합니다. 이 리스트에서 각 자리에 맞는 숫자를 선택해 나가면서 순열을 완성할 수 있습니다. 또한 k는 1부터 시작하는 값이므로, 0 기반으로 맞추기 위해 k 값을 1 감소시켜줍니다.
List<Integer> numbers = new ArrayList<>(); // 1부터 n까지의 숫자를 저장할 리스트
for (int i = 1; i <= n; i++) {
numbers.add(i); // 후보 리스트에 숫자 추가
}
k--; // 0-based로 맞추기 위해 k를 1 감소
5. 각 자리에 대한 k번째 후보 선택
이제 각 자리에서 팩토리얼을 이용해 후보 리스트에서 선택할 숫자를 결정합니다. 팩토리얼을 통해 선택 가능한 조합의 수를 계산하고, 그 값을 이용해 k번째 순열의 각 자리에 올 숫자를 정합니다. 선택된 숫자는 결과 배열에 추가하고, 후보 리스트에서는 제거됩니다.
for (int i = 0; i < n; i++) {
long factorial = factorial(n - i - 1); // 남은 자리 수에 대한 팩토리얼
int index = (int)(k / factorial); // k를 팩토리얼로 나눈 몫이 현재 자리에 올 숫자의 인덱스
result[i] = numbers.remove(index); // 그 숫자를 결과 배열에 추가하고, 후보군에서 제거
k %= factorial; // 나머지로 k 갱신
}
6. 최종 결과 도출
모든 자리의 숫자를 선택한 후, 완성된 배열이 k번째 순열이 됩니다. 이 배열은 사전 순으로 k번째에 해당하는 순열을 나타내며, 이를 반환하면 k번째 줄 서는 방법을 구할 수 있습니다.
// k번째 순열을 반환
return result;
Complexity
- ⏳ TC: O(n^2)
- 💾 SC: O(n)
팩토리얼을 계산하고, 리스트에서 숫자를 제거하는 과정은 각각 O(n)입니다. 이 과정은 n번 반복되므로 시간 복잡도는 O(n^2)입니다. 공간 복잡도는 숫자와 결과 배열을 저장하는 데 O(n)이 사용됩니다.
- Algorithm
- Math