next_permutation 구현

Next Permutation

next permutation !  말 그 대로 다음 순열을 찾는 방법이다. 

= 현재 순열의 상태에서 크기순으로(사전 순) 다음에 올 수 있는 순열을 생성

 

구현에 들어가기 전에 기억 할 것

• 첫 순열 = 오름차순
• 마지막 순열 = 내림차순 

      → 모든 수가 내림차순으로 정렬되어 있다면, 순열을 모두 만들어 낸 것이고, 따라서 종료 조건이다!

 

그렇다면, Next Permutation을 어떻게 구현할까?

1. 뒤에서부터 역방향으로 탐색하면서 교환위치( i-1 , 오름차순이 깨지는 부분)을 찾는다.

💡 오름차순이 깨지는 부분이 교환 위치인 이유

자 예를 들어 ` int a = {1, 4, 9, 8, 3, 2,1}; ` 배열이 있다고 하자.
a[2] ~ a[6] 은 모두 내림차순으로 정렬되어 있다.
따라서, 더 이상 다음 순열이 발생할 수 없고,
새 순열을 만들기 위해서는 a[1] ~ a[6] 을 이용해서 만들어야 한다.

때문에, a[1] 이 교환 위치인 것이다.

 

2. 다시 뒤에서 부터 역뱡향으로 탐색하면서, 교환할 값의 위치(j)를 찾는다.

    이 때 교환할 값은 역방향으로 탐색할 때, 처음으로 등장하는 a[i-1] 보다 큰 수 이다.

💡 교환할 값의 위치를 위와 같이 정하는 이유는
    해당 순열보다 큰 순열들 중에서 가장 작은 순열을 찾기 위해서이다.

 

3. 두 값을 교환한다.

 

4. 교환위치 (i) 부터 맨 뒤 까지 오름차순으로 정렬한다.

💡 정렬 방법
앞서 2번에서, 교환할 값을 처음으로 등장하는 a[i-1]보다 큰수로 지정했다.
그렇다면, 역방향에서 볼 때, last_idx ~ i 까지의 부분 수열은 자동으로 오름차순이 된다.
따라서 (last_idx - i + 1) / 2 만큼 반복문을 돌면서 정렬해주면 된다! 자세한 건 코드를 보자!

 

 

 

구현

import java.util.*;

// nPn
public class PermutaitionNPTest {

	static int N, R;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();

		int[] input = new int[N];
		for(int i=0; i<N; i++) input[i] = sc.nextInt();
		Arrays.sort(input); // 전처리 : 오름차순 정렬
		
		do {
			System.out.println(Arrays.toString(input));
			
		} while(np(input));
		
		sc.close();
	}
	
	private static boolean np(int[] input) {
		
		int n = input.length;
		
		// step1. 뒤쪽부터 꼭대기를 찾는다. (꼭대기 바로 앞이 교환할 자리)
		int i = n-1;
		while(i>0 && input[i-1]>=input[i]) --i;
		if(i == 0) return false;
		
		// step2. 꼭대기 바로 앞(i-1) 자리에 교환할 값을 뒤쪽부터 찾는다.
		int j = n-1;
		while(input[i-1]>=input[j]) --j;
		
		// step3. 꼭대기 바로 앞(i-1) 자리와 그 자리 값보다 한단계 큰 자리 (j) 수와 교환
		swap(input, i-1, j);
		
		// step 4. 꼭대기부터 맨 뒤 까지 오름차순으로 정렬
		int k= n-1;
		while(i<k) {
			swap(input, i++, k--);
		}

		return true;
	}
	
	private static void swap(int[] input, int i, int j) {
		int tmp = input[i];
		input[i] = input[j];
		input[j] = tmp;
	}
}

 

관련 문제

BOJ 5360번: Next Permutation

5360번: Next Permutation

import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		N = Integer.parseInt(br.readLine());
		
		String perm;
		for(int i=0; i<N; i++) {
			perm = br.readLine();
			sb.append(solution(perm)+"\n");
		}
		System.out.println(sb.toString());
		br.close();
	}

	static String solution(String perm) {
		
		int last_idx = perm.length()-1;
		char[] permArr = perm.toCharArray();
		
		// step 1 꼭대기를 찾음
		int i = last_idx;
		while(i>0 && permArr[i] <= permArr[i-1]) i--;
		if(i == 0) return "USELESS";
		
		// step 2 교환할 자리를 찾음
		int j = last_idx;
		while(j>0 && permArr[j] <= permArr[i-1]) j--;
		
		// step 3 swap
		swap(permArr, i-1, j);
		
		// step 4 sort
		int k = last_idx;
		while(i < k) swap(permArr, i++, k--);
		
		return new String(permArr);
	}
	
	static void swap(char[] permArr, int i, int j) {
		char tmp = permArr[i];
		permArr[i] = permArr[j];
		permArr[j] = tmp;
	}
}