(Java) Programmers 줄 서는 방법

 

- 목차

 

 

문제 링크.

https://school.programmers.co.kr/learn/courses/30/lessons/12936#

프로그래머스

 

문제 설명.

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! 이하의 자연수 입니다.

 

 

문제 분석.

해당 문제는 순열을 이해하고 구현할 수 있는지를 묻는 의도를 지닙니다.

단순히 Permutation 을 구하는 로직을 적용하여 접근한다면 반드시 시간이 초과하는 상황이 발생합니다.

왜냐하면 최악의 경우 k 는 20! 이 될 수 있고, 20! 의 값은 2432902008176640000 입니다.

그래서 해당 문제는 수학적인 방법으로 접근해야합니다.

 

만약 1, 2, 3, 4 인 수열을 순열로 표현한다면 어떻게 될까요?

모든 경우의 수를 표현할  수 는 없지만, 아래와 같이 표현됩니다.

1,2,3,4 // 1번째
1,2,4,3 // 2번째
1,3,2,4 // 3번째
1,3,4,2 // 4번째
1,4,2,3 // 5번째
1,4,3,2 // 6번째

2,1,3,4 // 7번째
2,1,4,3 // 8번째
2,3,1,4 // 9번째
2,3,4,1 // 10번째
2,4,1,3 // 11번째
2,4,3,1 // 12번째

...

4,3,2,1 // 24번째

 

여기서 주목할 점은 팩토리얼과 순서에 대한 관계인데요.

최종적으로 1,2,3,4 수열을 순열로 표현할 수 있는 가짓수는 4! = 24 입니다.

만약 가장 첫번째 값을 1로 고정하고 2,3,4 수열을 순열로 표현한다면

3! = 6 개가 됩니다.

이러한 6개의 순열들이 4가지가 모여 4 x 3! = 24 개인 경우의 수가 생깁니다.

 

그러하여 찾고자하는 k 번째 케이스가 6번째라면 1432 가 되고

7번째 케이스라면 2134가 됩니다.

6 과 7 을 경계로 첫번째 자릿수의 값이 변경됩니다.

그리고 12번째 값은 2431, 13번째 값은 3124 로

이 또한 12번째 값과 13번째 값을 경계로 첫번째 자릿수가 변경됩니다.

 

이를 수학적으로 표현하면 1 x 3! 와 1 x 3! + 1 은 첫번째 자릿수가 1 에서 2 로 변경됩니다.

그리고 2 x 3! 와 2 x 3! + 1 은 첫번째 자릿수가 2 에서 3 으로 변경됩니다.

 

이러한 패턴을 통해서 순열을 나타낼 수 있습니다.

 

문제 풀이.

아래의 코드가 좀 복잡할 수 있어서 로그를 찍어서 나타내보겠습니다.

import java.util.*;

class Solution {
    
    // 팩토리얼을 구하기 위한 함수입니다. 
    long factorial(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        return n * factorial(n - 1);
    }
    
    // k 와 Factorial(n) 사이의 관계를 나타내기 위한 함수입니다. 
    // 몫과 나머지를 반환합니다. 
    long[] getQuotientAndRemainder (int n, long k) {
        long factorialNumber = factorial(n);
        long quotient = k / factorialNumber;
        long remainder = k % factorialNumber;
        return new long[]{quotient, remainder};
    }
    
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        List<Integer> sequence = new ArrayList();
        // 초기화 
        for (int i = 0; i < n; i++) {
            sequence.add(i + 1);
        }
        
        // 0번부터 인덱싱하기 위하여 1을 뻄.
        k--;
        int index = 0;
        
        while (!sequence.isEmpty()) {
            
            // n 수열은 n! 개의 수열을 가집니다. 
            // 첫번째 값을 알아내기 위해서 k 와 factorial(n - 1) 의 관계를 알아야합니다. 
            long[] quotientAndRemainder = getQuotientAndRemainder(n - 1, k);
            long quotient = quotientAndRemainder[0];
            long remainder = quotientAndRemainder[1];
            
            int value = sequence.get((int) quotient);
            sequence.remove((int) quotient);
            answer[index] = value;
            k = remainder;
            index++;
            n--;
        }

        return answer;
    }
}

 

 

1,2,3,4 수열에서 8번째 값 찾기.

8번째 값은 2,1,4,3 입니다.

8은 1부터 시작한 순서이기 때문에 7로 표현하겠습니다.

먼저 7 은 3! 보다 크고 2 x 3! 보다 작습니다.

3! < 7 < 2 x 3! 이를 수열의 관점에서보면 첫번째 값이 2 라는 의미입니다.

이렇게 되면 8번째 수열은 2로 시작함을 알 수 있습니다.

그리고 3! 로 나눈 나머지가 1 이 되죠.

 

1을 다시 2! 로 나누어봅니다.

몫은 0 나머지는 1입니다.

그럼, 8번째 순열의 두번째 자릿수는 1 이 됩니다.

또 다시 1! 로 나누어보면

몫은 1 나머지는 0이 되고, 8번째 순열의 두번째 자릿수는 4 이 됩니다. 

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,2,3
1,4,3,2
2,1,3,4
2,1,4,3