[알고리즘]순열 - NextPermutation

요즘 블로그 글을 쓰는 주기가 길어진다. 써야지 하는 마음이 있다가도 지금 글을 쓰는게 사치는 아닌지 생각이 든다. 왜냐면 글을 쓰고 정리하는 시간에 문제 하나라도 더 풀고 혼자서 다시 풀어보는게 내 실력에 향상이 될텐데하는 조급합과, 블로그 글 쓸 시간이 있느냐 하는 죄책감....그래도 조금씩은 쓰자ㅠㅠ

오늘은 2차 과목평가도 있었고, 자바반으로 옮긴 후 처음 보는 시험인데 처음부터 떨어지고 싶지 않았기에 긴장하고 공부를 했다. 괜히 블로그 쓴다고 나대다가 떨어지면 너무 잔혹하잖아...그래서 그냥 따로 순열, 조합, 부분집합 혼자서 구현해보고 IM관련 백준을 풀면서 한주를 보냈고, 오늘 시험을 봐서 마음이 조금은 나아졌다.

 

시험을 본 오늘도 역시나 싸피는 진도를 나갔다. 오늘도 순열을 한다길래, 앗싸 개꿀~했는데 전혀 다른 순열이었다.

하나는 비트 마스킹을 이용한 것이었고, 또하나는 NextPermutation이란 것이었다. 비트 마스킹은 단순히 새로운 것이라 익숙해지기만 하면  되는거였지만, NextPermutation은 전혀 다른 방향애서 접근을 하는 거라 이해하는 것조차 힘이 들었다.(비트마스밍은 다음에 올리든가 하겠...! 어차피 코드는 깃허브에.)

그래서 NextPermutation 이해한 거 얼른 박제할 겸 블로그에 정리해보자.

 

다음 코드는 숫자 N이 주어지면 1~N까지의 모든 순열을 구하는 코드이다. 

public class NextPermutationTest {
	static int N;
	static int[] input;
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		input = new int[N];
		
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		
		//1. 오름차순 정렬
		Arrays.sort(input);
		
		do {
			//순열 출력
			System.out.println(Arrays.toString(input));
		}while(np());
	}

	private static boolean np() {
		
		//1. 교환위치 찾기
		int i = N-1;
		while( i>0 && input[i-1] >= input[i]) --i;		
		
		if(i==0) return false;
		
		//2. 교환위치에 교환할 값 찾기
		int j = N - 1;
		while(input[i-1] >= input[j]) --j;
		
		//3. 교환위치와 교환할 값 교환하기
		swap(i-1,j);
		 
		//4. 교환위치 뒤(꼭대기)부터 맨 뒤까지 만들수있는 가장 작은 순열 생성(오름차순정렬)
		int k = N-1;
		while(i<k) {
			swap(i++, k--);
		}
		return true;
	}
	
	public static void swap(int i, int j) {
		int temp = input[i];
		input[i] = input[j];
		input[j] = temp;
	}
}

 

로직을 이해하자. 1 2 3 4 5가 있는데 이걸 nPn해보자. 즉 5가지의 모든 순열을 구해보자

 

스텝1) 전체 오름차순 정렬

1 2 3 4 5

스텝2) 젤 꼭대기 i를 구하자. 현재는 4( = N-1)임.

스텝3) 꼭데기 바로 앞(i -1)보다 뒤에 있으면서 크기가 큰 숫자를 맨 뒤부터 앞으로 오면서 찾고 그 둘을 swap!

1 2 3 5 4

스텝4) 윗단계에서 swap하면 이제 i부터 끝까지는 뒤죽박죽 정렬임. 다시 오름차순으로 정렬(= 가장 작은 수로 만듦)하고 프린트

프린트: 1 2 3 5 4 (현재는 i+1이 4 하나라서 그대로임)

 

---위 단계 반복해보면

1 2 4 5 3 (스텝3, i = 3) 

1 2 4 3 5 (스텝4) - 출력

1 2 4 5 3 (스텝3, 스텝4) - 출력

1 2 5 4 3 (스텝3, i=2)

1 2 5 3 4 (스텝4) - 출력

1 2 5 4 3 (스텝3, 스텝4) - 출력

1 3 5 4 2 (스텝3)

1 3 2 4 5 (스텝4) - 출력

1 3 2 5 4 (스텝3,4)-출력

1 3 4 5 2 (스텝3)

1 3 4 2 5 (스텝4) - 출력

1 3 4 5 2(스텝3,4)-출력

1 3 5 4 2 (스텝3)

1 3 5 2 4 (스텝4)-출력

...아 머리아파 암튼 이렇게 되는것임. 천천히 보면 규칙이 보인다.

 

꼭 이렇게 안하고 일반적인 순열구하는 방법으로 해도 상관없지만, 이렇게 하면 조합도 똑같은 방식으로 할 수 있어서 편하다고 한다.

단, 속도는 NextPermutation이 10배정도 더 빠름. 왜냐면 일반적인 아래의 순열코드는 일단 for(int i=0; i<n; i++)하면서 중복체크를 하는데 일단 ㄹㅇ n번 다 들어가서 봄. 그러나 ,NP는 정확히 딱 그 순열만큼만 돈다.

그럼 NP가 무조건 좋나? 노노 NP는 nPr이 안됨. 무조건 nPn밖에 못한다.

 

---------다음은 원래 전통적인 순열구하는 방식코드

import java.util.Arrays;
import java.util.Scanner;

// nPr
// n개의 수 입력받아 처리
public class PermutationTest {

	static int N,R;
	static int[] input, numbers; // input : 입력수배열, numbers : 선택수배열
	static boolean[] isSelected;
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();
		
		input = new int[N];
		numbers = new int[R];
		isSelected = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		
		permutation(0);
	}
	
	//  현재 자리에 수 뽑기
	public static void permutation(int cnt) { // cnt : 직전까지 뽑은 수개수
		
		// 기본파트
		if(cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		// 입력받은 모든 수를 현재 자리에 넣어보기
		for (int i = 0; i < N; i++) {
			// 기존자리의 수들과 중복되는지 체크
			if(isSelected[i]) continue;
			
			numbers[cnt] = input[i];
			isSelected[i] = true;
			// 다음수 뽑으러 가기
			permutation(cnt+1);
			isSelected[i] = false;
		}
	}

}