백준 알고리즘 - 9742 순열

www.acmicpc.net/problem/9742

9742번: 순열

 

  혹시 NextPermutation이라고 아시나요?

저도 최근에서야 배운 일종의 순열을 만드는 방법 중 하나입니다.

 

 

  이 방법은 우선 입력될 Array가 오름차순으로 sort 되어있어야만 유의미한 알고리즘입니다.

 

 

public static boolean nextPermutation(char[] arr, int N) {
	int i = N - 1;
	while(i > 0 && arr[i-1] >= arr[i]) --i;
	if(i == 0) return false;
	
	int j = N - 1;
	while(arr[i-1] >= arr[j]) --j;
	swap(arr, i-1, j);
	
	int k = N - 1;
	while(i < k) {
		swap(arr, i++, k--);
	}
	return true;	
}
	
public static void swap(char[] arr, int i, int j) {
	char temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

  

  예를 들어 오름차순으로 정렬되어 있는 {1, 2, 3, 4}라는 Array가 있을 때, 우선 method 안으로 들어가면 맨 오른쪽 index인 N-1을 i에 저장하여, i-1번째 값이 i번째 값보다 작아질 때까지 i를 1씩 빼줍니다. 그러면 오른쪽에서 마지막으로 할당된 i까지의 값 중에서는 i번째 값이 가장 크게 됩니다.

{1, 2, 3, 4} 에서는 i가 3이 되겠군요.

 

 

  이후에는 다시 N-1을 j라는 곳에 넣고 이번에는 i-1번째 값보다 큰 값을 찾으며 j를 1씩 빼줍니다. 이후 두 값의 위치를 바꿔줍니다.

 

 

  마지막으로 N-1번째 값부터 i번째 값과 서로 1칸씩 가까워지며 값을 바꿔줍니다. 설명만 들으면 정말 뭔지 모르겠지만 한번 단계별로 차근차근 진행해보겠습니다.

 

 

==============================
1번째 단계		

[1 2 3 4]
       i

[1 2 3 4]
    i-1  
       j

i-1과 j를 swap		

[1 2 4 3]
       i
       k

i == k이므로 종료

1번째 단계 종료	
==============================

 

==============================
2번째 단계

[1 2 4 3]
     i
     
[1 2 4 3]
  i-1  j
  
i-1번째와 j번째를 swap

[1 3 4 2]
     i k

[1 3 2 4]
     k i
     
i > k이므로 종료

2단계 종료
==============================

 

==============================
3번째 단계

[1 3 2 4]
       i     
     
[1 3 2 4]
    i-1j
  
i-1번째와 j번째를 swap

[1 3 4 2]
       i
       k

i == k이므로 종료

3단계 종료
==============================

 

 

  이렇게 method 시작 전의 [1, 2, 3, 4], 1단계 이후의 [1, 2, 4, 3], 2단계 이후의 [1, 3, 2, 4], 3단계 이후의 [1, 3, 4, 2] ...

이런 식으로 계속해서 오름차순의 순열을 한번 실행할 때마다 1개씩 내뱉게 됩니다.

 

 

  NextPermutation의 특징은 바로 순열을 '오름차순'으로 만들 수 있다는 것과 속도가 일반적으로 재귀로 구현한 것보다

더 빠르다는 것입니다.

  단점으로는 nPn밖에 구할 수 없다는 점이네요.

 

 

  이번 문제는 NextPermutation을 구현해서 풀면 쉽게 풀리는 문제입니다. C++에는 API로 존재한다는데 왜 Java에는 없는걸까요...?

 

 

  그러나 그 밖에 이 문제의 다른 점은 입력을 무한히 받는다는 점입니다. 평소에 알고리즘 문제를 풀 때에는 항상 입력될 크기를 미리 알려줘서 해당 크기에 맞도록 입력받을 수 있게 만들어 놓는데, 이번 문제는 언제까지 입력을 받을 수 있는지 모르는 상태에서 입력을 받아야 합니다.

  그래서 br.readLine()을 이용해 입력을 받되, 만일 입력될 값이 없어 NullPointerError가 발생할 때는 try ~ catch로 잡아주어 에러가 발생하더라도 프로그램이 에러를 토하며 종료되지 않도록 만들었습니다.

 

 

아래는 문제의 풀이 코드입니다.

 

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

public class Main_BJ_9742_순열 {

	public static void main(String[] args){
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk;
		
		try {
			while((tk = new StringTokenizer(br.readLine(), " ")) != null) {
				int flag = 0;
				String str1 = tk.nextToken();
				char[] input = new char[str1.length()];
				String str2 = "";
				
				for(int i = 0; i < str1.length(); i++) {
					input[i] = str1.charAt(i);
				}
				
				int N = Integer.parseInt(tk.nextToken());
				
				for(int i = 0; i < N-1; i++) {
					if(nextPermutation(input, input.length) != true) {
						str2 = "No permutation";
						flag = 1;
						break;
					}
				}
				
				if(flag == 0)
					System.out.println(str1 + " " + N + " = " + String.valueOf(input));
				else
					System.out.println(str1 + " " + N + " = " + str2);
			}
		}catch(NullPointerException e) {
			
		}catch(Exception e) {
			
		}
	}
	
	public static boolean nextPermutation(char[] arr, int N) {
		int i = N - 1;
		while(i > 0 && arr[i-1] >= arr[i]) --i;
		if(i == 0) return false;
		
		int j = N - 1;
		while(arr[i-1] >= arr[j]) --j;
		swap(arr, i-1, j);
		
		int k = N - 1;
		while(i < k) {
			swap(arr, i++, k--);
		}
		
		return true;
		
	}
	
	public static void swap(char[] arr, int i, int j) {
		char temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}