다음 순열 (Next Permutation) Java

Next Permutation

시간 복잡도 O(n)
어떠한 순열의 다음 순열을 구하는 알고리즘입니다.

예제로 알아봅시다.

 

이 수열의 다음 수열을 구하려고 합니다.

 

처음 떠오르는 방법은 2, 3, 4, 5, 7을 나열해서 만들 수 있는 순열을 모두 구해서

2, 5, 7, 4, 3의 다음 순열을 알아내는 방법입니다.

이 방법은 너무 비효율적일 것입니다..

 

next permutation 알고리즘으로 O(n)의 시간복잡도로 다음 순열을 구할 수 있습니다.

 

1) 뒤에서부터 탐색하면서, 처음으로 *감소하는* 부분의 인덱스를 구합니다.

예제에서는 array[1] == 5 입니다.

이 인덱스를 편의상 i라고 칭하겠습니다.

 

2) 다시 뒤에서부터 탐색하면서, '감소하는 부분'보다 큰 값을 가진 인덱스를 구합니다.

예제에서는 array[2] == 7 입니다. 5보다 큰 값이 가장 처음 나타나는 부분이기 때문입니다.

이 인덱스를 편의상 j라고 칭하겠습니다.

 

3) array[i], array[j] 값을 스왑합니다.

그러면 예제는 2, 7, 5, 4, 3 이 됩니다.

 

4) i+1번째부터 끝까지 오름차순 정렬해줍니다.

예제에서는 인덱스 2~4를 정렬하는 것입니다.

그러면 결과는 2, 7, 3, 4, 5 로, 처음 값의 다음 순열을 정확하게 구할 수 있습니다.

 

아래는 자바로 구현한 코드입니다. ^^

char[] arr = new char[n+1];

// 모든 경우의 수를 다 만들고 찾으면 시간초과
// 뒤에서부터 체크
int index = arr.length-1;
for(int i=arr.length-1; i>0; i--) {
    // 내 앞의 글자가 나보다 작아진 경우의 인덱스를 저장
    if(arr[i] > arr[i-1]) {
        index = i-1;
        break;
    }
}

// 다시 뒤에서부터 체크
for(int i=arr.length-1; i>index; i--) {
    // arr[index]보다 큰 문자 찾기
    if(arr[i] > arr[index]) {
        // 두 문자 위치 바꿔주기
        swap(i, index);
        break;
    }
}

// arr[index] 뒷부분은 정렬해주세요
Arrays.sort(arr, index+1, arr.length);