[JAVA] 백준 1722 조합

 

 

 

1722번: 순열의 순서

문제

k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

풀이

📌 factorial 배열 만들기

        long[] A = new long[N+1];
        A[0] = 1;
        for(int i=1; i<N+1; i++){
            A[i] = A[i-1] * i;
        }

문제를 해결하면서 팩토리얼을 사용할일이 많기 때문에 N까지의 팩토리얼들을 미리 구해주었다.

이 방식은 합배열을 만드는 방식과 동일하고 다른 점은 곱을 이용한다는 점이다.

📌 문제 1 : 순열의 위치(1번째, 2번째)가 주어졌을 때 순열을 구하시오

if(st.nextToken().equals("1")){
    long th = Long.parseLong(st.nextToken()) - 1;
    for(int i=N; i > 0; i--){
        long ith = th / A[i-1] + 1; // 현재 자릿수에서 몇 번째인지 찾는다.
        th %= A[i-1]; // 다음 자리 수를 계산하기 위해 갱신해준다.
        long count = 0;  // 현재 수가 몇 번째 자리수 인지 카운트하기 위해 사용
        int index = 0;  // 현재 인덱스를 가르킨다.
        while (count != ith){ // 찾고자 하는 x번째 수라면 반복을 멈춘다.
            index++; // 배열을 모두 돌면서 방문한 적이 없는 수가 있다면 카운트해준다.
            if(!V[index]) count++; 
        }
        V[index] = true;  // 현재 수의 방문을 체크해주고 현재 수를 출력으로 담는다.
        sb.append(index).append(" ");
}

• 각 자리수가 제거될 때 마다 N-1 팩토리얼 만큼의 경우의 수가 남는다.
  • 예를들어 N = 4일때, 수열의 경우의 수는 4! = 24가지가 있고 첫 번째 자리수가 1, 2, 3, 4 중에 하나가 선택되었을 때 각 경우의 수는 N-1! = 3! = 6가지씩 있다.
  • 여기서 두 번째 자리수가 선택되었을 때 각 경우의 수는 N-2! = 2! = 2가지씩 있다.
• 받아온 값에서 1을 빼주는 이유는 4자리가 있는 경우에서 첫째 자리는 1 ~ 4번째까지 존재하지만 6으로 나누었을 때는 0 ~ 4번째가 존재한다. 따라서 이 문제를 해결하기 위해 받아온 값에서 1을 빼줌으로써 0 ~ 3번째까지 나오게 되고, ith 값에서 1을 더해줌으로써 1 ~ 4번째 까지의 수가 나올 수 있도록 해준다.

따라서 각 자리수가 선택될 때마다, 몇 번째 수인지 알아낸 다음 앞의 자리수에서 선택되지 않은 수들 중 선택하면 된다.

📌 문제 2 : 순열이 주어졌을 때 순열의 위치(1번째, 2번째)를 구하시오

        }else{
            long th = 1;
            for(int i=N; i>0; i--){
                int data = Integer.parseInt(st.nextToken());
                int index = 0;
                int count = 0;
                while (index != data){
                    index++;
                    if(!V[index]) count++;
                }
                V[index] = true;
                th += (count-1) * A[i-1];
            }
            sb.append(th);
        }

가장 첫 자리수부터 값이 몇 번째인지 찾는다.

• 4자리가 있는 순열에서 1 3 2 4라는 순열이 주어졌을 때는 다음과 같다.
• 1 : index와 count로 1이 몇 번째인지 찾는다. 1은 1, 2, 3, 4중에서 1번째 이며 1을 방문한 것을 체크해준다. 그 후 몇 번째 값인지를 담고 있는 th에 1 - 0 * 3!을 해준다. 1은 1 ~ 6까지의 순열이고 2는 7 ~ 12까지의 순열이기 때문에 팩토리얼과 곱해주는 것이다.
• 3 : 남아있는 2, 3, 4중에서 3이 몇 번째 인지 찾는다. 3은 2번째이다. 따라서 (2 - 1) * 2!을 해주고 2을 th에 더한다.
• 2 : 남아있는 2, 4 중에서 2는 1번째 이므로 0 * 1!을 더해준다.
• 4 : 남아있는 4 중에서 4는 1번째 이므로 0 * 1!을 더해준다.

여기서 th를 1로 초기화 해주는 이유는 위에서 계산한 값이 0 ~ 23이 결과로 나오기 때문이다.

📌 전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        boolean[] V = new boolean[N+1];
        long[] A = new long[N];
        A[0] = 1;
        for(int i=1; i<N; i++){
            A[i] = A[i-1] * i;
        }

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        if(st.nextToken().equals("1")){
            long th = Long.parseLong(st.nextToken()) - 1;
            for(int i=N; i > 0; i--){
                long ith = th / A[i-1] + 1;
                th %= A[i-1]; 
                long count = 0; 
                int index = 0;
                while (count != ith){ 
                    index++; 
                    if(!V[index]) count++; 
                }
                V[index] = true;
                sb.append(index).append(" ");
            }
        }else{
            long th = 1;
            for(int i=N; i>0; i--){
                int data = Integer.parseInt(st.nextToken());
                int index = 0;
                int count = 0;
                while (index != data){
                    index++;
                    if(!V[index]) count++;
                }
                V[index] = true;
                th += (count-1) * A[i-1];
            }
            sb.append(th);
        }

        System.out.println(sb);

    }

}

결과