[BaekJoon] 1722 순열의 순서 (Java)

1.  문제 링크

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

2.  문제

요약

• 1부터 N까지의 수를 임의로 배열한 순열은 총 N!가지가 있고 임의의 순열은 정렬을 할 수 있습니다.
• 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두번 째 수도 같으면 세 번째 수가 작은 것이 앞서게 됩니다.
• N이 주어졌을 때, k가 주어지면 k번째 수열을 구하고 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지 출력하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 20보다 작거나 같은 N이 주어지고 두 번째 줄에 소문제 번호와 그에 따른 값이 주어집니다.
  • 소문제 번호가 1인 경우 1보다 크거나 같고 N!보다 작거나 같은 k가 주어집니다.
  • 소문제 번호가 2인 경우 임의의 순열을 나타내는 N개의 수가 주어집니다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타납니다.
• 출력: 첫 번째 줄에 k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static ArrayList<Integer> nums;
	static int N;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		int type = scanner.nextInt();
		nums = new ArrayList<>();
		for(int i = 1; i <= N; i++) {
			nums.add(i);
		}
		if(type == 1) {
			long numberth = scanner.nextLong();
			findSeries(numberth);
		} else if(type == 2) {
			ArrayList<Integer> series = new ArrayList<>();
			for(int i = 0; i < N; i++) {
				series.add(scanner.nextInt());
			}
			findNumberth(series);
		} else {
			System.exit(1);
		}
	}
	
	static void findSeries(long numberth) {
		ArrayList<Integer> series = new ArrayList<>();
		numberth -= 1;
		int cipher = N - 1;
		while(cipher > 0 || nums.size() > 0) {
			long fact = calcFactorial(cipher);
			long quotient = numberth / fact;
			numberth %= fact;
			series.add(nums.get((int)quotient));
			nums.remove((int)quotient);
			cipher--;
		}
		for(int s : series) sb.append(s).append(' ');
	}
	
	static void findNumberth(ArrayList<Integer> series) {
		int cipher = N - 1;
		long numberth = 1;
		for(int i = 0; i < series.size() - 1; i++) {
			int cur_num = series.get(i);
			int idx = nums.indexOf(cur_num);
			if(idx != 0) {
				long fact = calcFactorial(cipher);
				numberth += fact * idx;
			}
			nums.remove(idx);
			cipher--;
		}
		sb.append(numberth).append('\n');
	}
	
	static long calcFactorial(long num) {
		long result = 1;
		for(long i = 2; i <= num; i++) {
			result *= i;
		}
		return result;
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb.toString());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}

4.  접근

• 두 개의 소문제가 있고 각각에 대해서 살펴보겠습니다.

1. 소문제 번호가 1인 경우
   • 주어진 k번째 순열을 찾는 문제입니다.
   • N이 주어지면, 1부터 N을 담을 ArrayList nums를 생성하고 nums에 1부터 N까지의 수를 순서대로 담습니다.
   • k번째 순열을 저장할 ArrayList series를 생성합니다.
   • 문제에서 언급되었다시피 수가 N개라면 N!개의 순열을 생성할 수 있습니다.
   • 순열에서 첫 번째 자리가 결정되었다면 남은 숫자들로 만들 수 있는 순열은 (N - 1)!개가 됩니다.
   • 이를 이용하여 각 자리의 수를 하나씩 결정합니다.
   • 첫 번째 자리를 결정할 때는 (N - 1)!을 구하고 k를 이로 나눈 후에, nums에서 k / (N - 1)!의 몫이 index인 값을 뽑고 이를 series에 넣어준 뒤 해당 수를 nums에서 삭제합니다. 이 수가 첫 번째 자리의 수가 됩니다.
     • 구한 수를 series에 넣은 뒤에 nums에서 삭제하는 이유는 이후 자리수에서의 수를 구할 때, 해당 수는 사용할 수 없기 때문에 해당 index 위치에는 그 다음 수가 위치해야하기 때문에 삭제합니다.
   • k는 k를 (N - 1)!으로 나눈 후의 나머지로 업데이트합니다.
   • 그 다음 자리를 구할 때는 (N - 2)!을 구한 뒤에 같은 과정을 반복하여 해당 자리수의 수를 구하고 k를 업데이트해줍니다.
   • 이 과정을 마지막 자리수까지 진행하여 전체 자리수를 구합니다.
   • 이를 findSeries() 함수에서 구현하였습니다.
     
     
2. 소문제 번호가 2인 경우
   • 임의의 순열이 주어졌을 때, 몇 번째 순열인지 구하는 문제입니다.
   • N이 주어지면, 1부터 N을 담을 ArrayList nums를 생성하고 nums에 1부터 N까지의 수를 순서대로 담습니다.
   • 주어진 순열을 ArrayList series에 담습니다.
   • 첫 번째 자리의 수부터 확인하면서 각 자리수의 수가 정해졌다고 했을 때 만들어질 수 있는 순열의 개수를 이용하여 개수를 더해가면서 몇 번째 순열인지 찾습니다.
   • 예를 들어 첫 번째 자리에 대해서 구해보면 첫 번째 자리 수가 nums에서 어디에 위치하는지 찾습니다. 해당 index를 idx에 저장합니다.
   • 첫 번째 자리 수가 정해졌기 때문에 이럴 경우 (N - 1)!개의 순열을 구할 수 있기 때문에 (N - 1)!을 구하고 이 수에 idx를 곱하면 첫 번째 수가 정해졌을 때 그 이전까지 몇 개의 순열을 지나왔는지 알 수 있습니다. index는 0부터 시작하기 때문에 idx를 그대로 곱해주면 이를 구할 수 있게 됩니다.
   • 그리고 nums에서 첫 번째 자리 수를 제거하고 다음 자리수의 수를 확인합니다.
     • nums에서 해당 수를 제거하는 이유는 이후에 해당 수는 사용되지 않을 것이며 해당 수가 nums에 그대로 존재하게 된다면 이후에 수를 구할 때 index가 밀리는 경우가 생길 수 있기 때문에 제거해줍니다.
   • 위 과정을 첫 번째 자리 수부터 마지막에서 하나 앞의 자리 수까지 진행하여 각 자리수에서 수가 정해졌을 때 그 이전까지 몇 개의 순열을 지나왔는지 구하여 이 개수를 누적합니다.