코딩 테스트 [조합] - 순열의 순서 구하기

1부터 N까지의 수를 임의로 배열한 순열의 경우의 수는 N!이다. 임의의 순열은 영문 사전의 정렬 방식과 비슷하게 정렬된다고 하자. 예를 들면 N = 3이면 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2},{3, 2, 1}의 순서로 정렬된다. N이 주어지면 다음 두 소문제 중 1개를 푸는 프로그램을 작성해 보자.

• 소문제 1 : K가 주어지면 K번째 순열을 구한다.
• 소문제 2 : 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지 구한다.

(시간 제한 2초)

---

입력

1번째 줄에 순열의 개수 N(1 ≤ N ≤ 20), 2번째 줄의 1번째 수는 소문제의 번호다. 1일 때 K를 입력받고, 2일 때 임의의 순열을 나타내는 N개의 수를 입력받는다. 여기서 N개의 수에는 1에서 N까지의 정수가 한 번씩만 나타난다.

출력

주어진 소문제와 관련된 정답을 출력한다.

예제 입력
4	// 자릿수 N
1 3	// 소문제 번호, K
 
예제 출력
1 3 2 4

----

예제 입력
4	// 자릿수 N
2 1 3 2 4	// 소문제 번호, 순열
 
예제 출력
3

---

1단계 - 문제 분석하기

이 문제는 조합 문제와는 다르게 순열의 개념을 알아야 풀 수 있다. 순열은 순서가 다르다면 다른 경우의 수로 인정된다. N자리로 만들 수 있는 순열의 경우의 수를 구해야 한다는 것이 이 문제의 핵심이다.
4자리로 표현되는 모든 경우의 수를 구하는 예제를 살펴보겠다.

각 자리에서 구한 경우의 수를 모두 곱하면 모든 경우의 수가 나온다. 4자리로 표현되는 모든 경우의 수는 4 $*$ 3 $*$ 2 $*$ 1 = 4! = 24이다. 이를 일반화하면 N자리로 만들 수 있는 순열의 모든 경우의 수는 N!이라는 것을 알 수 있다.

2단계 - 손으로 풀어 보기

1 자릿수에 따른 순열의 경우의 수를 1부터 N자리까지 미리 계산한다.

2 소문제 1을 풀어 보겠다. 첫번째 예제를 이용해 K번째 순열을 구한다.

K번째 순열 출력하기

1. 주어진 값(K)과 현재 자리(N) - 1 에서 만들 수 있는 경우의 수를 비교한다.
2. 1에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다(순열의 순서를 1씩 늘림).
3. K가 더 작아지면 순열에 값을 저장하고 K를 K - (경우의 수 * (cnt - 1))로 업데이트한다.
4. 순열이 완성될 때까지 1 ~ 3을 반복하고 완료된 순열을 출력한다.
   

3 소문제 2를 풀어 보겠다. 예제 2를 이용해 입력된 순열의 순서 K를 구해 보겠다.

입력된 순열의 순서 구하기

1. N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인한다(현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자).
2. 해당 순서 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 더한다.
3. 모든 자릿수에 관해 1 ~ 3 을 반복한 후 K값을 출력한다.
   

3단계 - sudo코드 작성하기

F(각 자리별로 만들 수 있는 경우의 수 저장하기)
S(순열을 담는 배열) visited(숫자 사용 유무 저장 배열)
N(순열의 길이)
Q(문제의 종류)

if(Q == 1)
{
	K(몇 번째 순열을 출력할지 입력받기) -> 길이가 N인 순열의 K번째 순열 출력
    for(i -> N 만큼 반복)
    {
    	cnt = 1;
        for(j -> N 만큼 반복)
        {
        	if(이미 사용한 숫자라면)
            	continue;
            
            if(현재 순서(K) < 해당 자리-1 순열 수 * cnt)
            {
            	현재 순서 = 현재 순서 - (해당 자리-1 순열 수 * (cnt-1))
                현재 자리에 j 저장, j를 사용 숫자로 체크
                break;
            }
            cnt++
        }
    }
    배열 출력
}
else if(Q == 2)
{
	K(순열의 순서 저장 변수)
    S(순열 배열 저장)
    for(i -> N만큼 반복)
    {
    	cnt = 0
    	for(j -> S[i]수만큼 반복
        {
        	if(j를 아직 사용하지 않았다면)
            	cnt++
        }
        
        K = K + cnt * 현재 자릿수-1에서 만들 수 있는 경우의 수
        S[i]번재 숫자를 사용 숫자로 변경
    }
    K 출력
}

4단계 - 코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q81 {
    public static void main(String[] args) throws IOException{
        int N, Q;
        long F[] = new long[21];
        int S[] = new int[21];
        boolean[] visited = new boolean[21];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        Q = Integer.parseInt(st.nextToken());

        F[0] = 1;
        for(int i = 1; i < N+1; i++){
            F[i] = F[i - 1] * i;        // 팩토리얼 형태로 저장
        }

        if(Q == 1){
            long K = Long.parseLong(st.nextToken());

            for(int i = 1; i < N+1; i++){
                int cnt = 1;
                for(int j = 1; j <= N+1; j++){
                    if(visited[j])
                        continue;

                    if(K <= cnt * F[N - i]) {
                        K = K - ((cnt - 1) * F[N - i]);
                        S[i] = j;
                        visited[j] = true;
                        break;
                    }

                    cnt++;
                }
            }

            for(int i = 1; i < N+1; i++){
                System.out.print(S[i] + " ");
            }

        }else if(Q == 2){
            long K = 1;

            for(int i = 1; i < N+1; i++){
                S[i] = Integer.parseInt(st.nextToken());
                int cnt = 0;

                for(int j = 1; j < S[i]; j++){
                    if(visited[j] == false)
                        cnt++;
                }

                K = K + cnt * F[N - i];
                visited[S[i]] = true;
            }

            System.out.println(K);
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편