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

 

안녕하세요 프로그래머스 Lv.2 정답률 47% 문제를 풀겠습니다.

이 문제는 순열과 팩토리얼의 개념을 활용하여 특정 순서의 배열을 찾는 문제입니다. 사람 수 'n'과 자연수 'k'가 주어졌을 때, 사전 순으로 나열했을 떄 'k' 번째의 배열을 찾는 것이 목표입니다.

 

이 문제는 n명의 사람이 줄을 서는 모든 경우의 수를 찾고, 그 중 k번째를 반환하는 문제입니다. 예를 들어, 3명의 사람이 있으면 가능한 줄 서는 방법은 총 6가지가 있습니다. 이러한 경우의 수는 팩토리얼을 사용하여 해결할 수 있습니다.

 

1. 먼저 'n'에 대한 팩토리얼 값을 구합니다.

2. '1'부터 'n'까지의 숫자를 포함하는 리스트를 생성합니다.

3. 'k-1' 을 현재 위치의 숫자들 개수의 팩토리얼로 나눈 몫을 사용하여 시작 숫자의 위치를 결정합니다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    long[] fact;

    public void factorial(int n) {
        fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }
    }

    public int[] solution(int n, long k) {
        factorial(n);

        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        int[] answer = new int[n];
        long remain = k - 1;

        for (int i = 0; i < n; i++) {
            if (numbers.size() == 1) {
                answer[i] = numbers.remove(0);
            } else {
                long currentFactorial = fact[numbers.size() - 1];
                answer[i] = numbers.remove((int) (remain / currentFactorial));
                remain %= currentFactorial;
            }
        }
        return answer;
    }
}

 

위 코드는 팩토리얼을 계산하고, 이를 활용하여 각 단계에서의 숫자 위치를 결정합니다.

'k-1'을 사용하는 이유는 인덱스가 0부터 시작하기 때문입니다. 이 방식은 팩토리얼과 순열의 기본 원리를 활용합니다.

 

이 문제는 팩토리얼과 순열에대한 이해가 필요한 문제로, 관련 지식이 없다면 시간이 걸릴 수 있습니다.