[C++] 순열 정렬방법 (next_permutation, prev_permutation)

본 포스팅은 Backjoon Online Judge의 "다음순열(10972), 이전순열(10973), 모든순열(10974), 차이를 최대로(10819)"를 함께 풀때 도움이 되는 글입니다.

C++의 STL에선 순열을 정렬하는 함수 next_permutation, prev_permutation이 존재한다.

가령, 1 2 3 4 라는 4개의 숫자로 이루어진 순열을 입력받았다고 가정할때

 

do{
	for(int i=0;i<n;i++){
    	cout << v[i] << " ";
    }
    cout << '\n';
} while (next_permutation(v.begin(), v.end()));

 

위와 같은 코드를 활용하면 다음과 같이 결과가 출력된다.

//출력 결과
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
...
...
4 3 2 1

 

반대로 역순(이전순열)으로 정렬을 하고 싶을 땐 위의 코드에서 next_permutation 대신 prev_permutation 을 사용하면 된다. 아래는 수정 코드의 출력 결과다.

 

// prev_permutation의 입력
4 3 2 1

// 출력 결과
4 3 2 1
4 3 1 2
4 2 1 3
4 2 3 1
...
...
1 2 3 4