[C++] next_permutation 알고리즘

알고리즘 문제를 풀다보면 순열과 조합을 구해야 하는 경우가 많다.

 

가령 다음과 같은 문제가 있다고 치자.

3, 4, 6으로 이루어진 수들 중 364보다 더 큰 수들 가운데 제일 작은 수를 구하시오

 

그럼 int arr[3] = {3, 4, 6}의 원소들을 순열로 구하면

{3, 4, 6}

{3, 6, 4}

{4, 3, 6}

{4, 6, 3}

{6, 3, 4}

{6, 4, 3}

 

이렇게 총 6가지가 존재해 {4, 3, 6}을 골라 436을 반환하면 된다.

 

next_permutation 알고리즘

https://en.cppreference.com/w/cpp/algorithm/next_permutation

std::next_permutation - cppreference.com

 

C++의 <algorithm> 헤더에는 순열을 구하는 next_permutation 함수가 있다.

template<class BidirIt>
	bool next_permutation(BidirIt first, BidirIt last);
    
template<class BidirIt, class Compare >
	bool next_permutation(BidirIt first, BidirIt last, Compare comp);

 

이 함수는 내부적으로 사전순으로 다음 순열을 생성한다.

그러면 위의 문제를 아래와 같이 풀 수 있다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

// 다음 순열을 찾는 함수
string getNextPermutation(string number) {
    // C++의 next_permutation을 사용하여 다음 순열을 찾음
    if (next_permutation(number.begin(), number.end())) {
        return number;
    } else {
        return ""; // 다음 순열이 없는 경우 빈 문자열 반환
    }
}

int main() {
    int N;
    cin >> N;
    
    // 숫자를 문자열로 변환
    string number = to_string(N);
    
    // 다음 순열을 찾음
    string nextNumber = getNextPermutation(to_string(N));
    
    cout << nextNumber << endl;

    return 0;
}

• 단순히 모든 순열의 경우의 수를 구하기 위해 do-while 문이랑 함께 쓰이는 경우도 많이 보인다.
• 이 함수를 아느냐 모르냐에 따라 속도차이가 굉장히 크다.
• 입력이 100만이어도 1초안에 반환하니 꼭 알아두자!