JAVA : nextPermutation 다음순열

nextPermutation 구현의 아이디어

nextPermuation이란 [1,2,3,4,5] ->[1,2,3,5,4] ->[1,2,4,3,5] 처럼 현재의 상태에서 다음 순열을 찾는 알고리즘이다.

물론 조합 알고리즘을 이용해서 각각의 인덱스의 조합을 이용해서 찾아도 되지만 더빠른 넥스트 퍼뮤테이션을 사용해야 할때가 있다.

 

기본 순열 1 3 5 4 2 에 대해서 예를 들어보자!

아래와 같은 순열이 이어저있을 때 nextPermutation은 다음과 같은 4가지 조건을 확인 하면된다.

모든 탐색은 오른쪽에서 왼쪽으로 시작한다.
1. arr[i-1] < arr[i] 이 오른쪽에서 왼쪽으로 탐색하면서 제일처음 나오는 값을 찾는다.
2. 이제 i-1를 비교하면서  arr[i-1] < arr[j] 를 만족하는 값을 찾는다. (오른쪽에서 왼쪽탐색시 처음나오는 값)
3. arr[i-1] 와 arr[j] 를 스왑한다.
4. i~N-1 까지의 순서를 reverse 해줍니다. (sort를 사용할 필요는 없고 양끝값을 swap해가면서 한칸식 줄여나갑니다)

아래와 같은 순열 있다고 생각하겠습니다.

arr[i-1] < arr[i] 를 만족하는 i-1를 찾는다.

arr[i-1]  기준으로 arr[j]를 만족하는 j값을 오른쪽부터 왼쪽으로 찾는다.

3. arr[i-1] 과 arr[j]를 swap

4. i~ j 까지의 순서를 reverse 해줍니다!

소스코드

import java.util.Arrays;
import java.util.Scanner;
 
public class PeumuTest {
 
    static int N;
    static int[] input;
    static int totalCnt=0;
 
    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();
        }
        
        // 시작 : 가장 작은 순열
        Arrays.sort(input);
        do {
            System.out.println(Arrays.toString(input));
        }while(nextPemutation());
        System.out.println("총 경우의 수 : "+totalCnt);
    }
    static boolean nextPemutation() {
        totalCnt++;
        // 맨 뒤부터 올라가면서 i-1<i 만족하는 것을 찾는다.
        int i = N - 1;
        // 현재의 내값보다 i-1이 커서 올라갈수 잇을때 까지 올라간다.
        while (i > 0 && input[i - 1] >= input[i])
            --i;
 
        if (i == 0)
            return false;
 
        int j = N - 1;
 
        // i 까지온다 왜냐 input[i-1] < input[i] 이기대문에 j는 최악의경우 i 까지온다.
        while (input[i - 1] >= input[j])
            --j;
 
        //i-1 과 j 스왑한다.
        int temp = input[i - 1];
        input[i - 1] = input[j];
        input[j] = temp;
        
        int k = N-1;
        while(i<k) {
            temp = input[i];
            input[i] = input[k];
            input[k] = temp;
            ++i;
            --k;
        }
        return true;
    }
}
 

출력은 do while 를 사용합니다. 이유는 nextPermutation은 다음 순열을 출력하기때문에 현재값을 출력을 하고 함수를 이용해서 다음 순열을 만듭니다.

while (input[i - 1] >= input[j]) 는 오른쪽 부터 탐색하면서 현재 i 가 i - 1 보다 더크다면 내려가는 구간 이기 때문에 i-- 하여서 다음 인덱스를 참고한다. while 문이 끝나면 arr[i-1] < arr[i]가 처음만족하는 배열이다.

만약 i = 0 이라면 현재 순열조합에서는 다음 순열을 찾을 수 없다. 따라서 false를 반환한다.

j값을 찾는것도 마찬가지다. j는 최악의 경우 i에서 멈춘다. 이유는 arr[i-1] < arr[i] 를 만족하는 값의 조건에서 찾는 것이기 때문이다.

그리고 arr[i-1] 과 arr[j]를 스왑한다.

이제 arr[i]~ arr[n-1] 를 역순으로 정렬한다.

k = n-1 이라고 할때
역순의 시작이 i 와  k 라고 한다면 두수를 스왑하고
i++; k--; 를 해주고 다시 스왑해서  i==k가 만날때 까지 해주면 그수는 reverese 형태를 띄게된다.  

 

백준 문제로는 다음문제가 있다.

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

10974번: 모든 순열