[백준] 1722 순열의 순서 - Java

 

 

 

문제 출저

https://www.acmicpc.net/problem/1722

1722번: 순열의 순서

 

 

 

문제 풀이

이 문제는 2가지 문제를 풀어야 합니다. 

첫 번째 입력은 n이 주어지고 두 번째 입력의 첫 번째 숫자는 어떤 문제를 풀어야 하는지 타입입니다.

1인 경우, k가 주어지며 k번째 순열을 구해야 합니다.

2인 경우, 순열이 주어지며 이 순열이 몇 번째 순서인지 구해야 합니다. 

문제의 n은 20이므로 일일히 다 순열을 구하면 20! 이 되므로 시간초과가 발생합니다. 

 

간격을 통해서 문제를 풀어야 합니다.

먼저, int[] factorial 을 n-1 크기로 만들어 1!, 2!, 3! 같이 각 수의 팩토리얼을 구합니다. 

문제 유형이 2번인 경우에 n = 4, int[] permutation = {1,3,2,4}가 주어졌을 때 예를 들어보겠습니다. 

 

각 자리의 숫자가 오기 까지 factorial[n-i-1] 반복됩니다. 

이게 무슨 말이냐면 1번째 자리인 1이 오기까진 factorial[4 - 0 - 1] * 0 이 반복된 것 입니다.

2번째 자리인 3이 오기까진 factorial[4 - 1 - 1] * 2이 반복된 것 입니다. 

 

이렇게 각 자리수가 오기까지의 횟수를 구하고 1부터 시작했기에 1을 더하면 문제를 풀 수 있습니다. 

 

1번 문제인 경우, 2번 문제를 반대로 풀면 구할 수 있습니다. 

 

저는 해당 블로그의 글을 참고했습니다.

https://dundung.tistory.com/60

백준 1722 순열의 순서 Java

 

 

 

소스 코드

package baekjoon.backjoon12.day0110.day08;


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

/*
순열의 순서
https://www.aczmicpc.net/problem/1722

20! 이라 일일이 구하면 시간 초과가 발생한다.

참고 사이트
https://dundung.tistory.com/60
 */
public class B1722 {

  static int n;
  static int type;

  static long[] factorial;
  static boolean[] check;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());

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

    factorial = new long[n+1];
    makeFactorial(n);
    check = new boolean[n+1];

    if(type == 1) {
      long index = Long.parseLong(st.nextToken());
      one(index);
    }
    else if(type == 2) {
      int[] numbers = new int[n];
      for(int i = 0; i < n; i++) {
        numbers[i] = Integer.parseInt(st.nextToken());
      }
      two(numbers);
    }
  }

  // 몇 번째인지 주어지고 순열이 뭔지 구해야한다.
  public static void one(long index) {

    int[] numbers = new int[n];

    for(int i = 0; i < n; i++) {
      for(int j = 1; j <= n; j++) {

        // 이미 사용되었으면 넘어간다.
        if(check[j]) continue;

        // 이 자리의 숫자가 들어갈 수 있다면 뺀다.
        if(factorial[n-i-1] < index) {
          index -= factorial[n-i-1];
        }
        else {
          numbers[i] = j;
          check[j] = true;
          break;
        }
      }
    }
    for(int i = 0; i < n; i++) {
      System.out.print(numbers[i] + " ");
    }
  }

  // 순열이 주어지고 몇 번째 인지 구해야 함
  public static void two(int[] numbers) {
    long index = 1;
    for(int i = 0; i < n; i++) {
      for(int j = 1; j < numbers[i]; j++) {
        if(check[j] == false) {
          index += factorial[n-i-1];
        }
      }
      check[numbers[i]] = true;
    }
    System.out.println(index);
  }

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





}