[백준 10974] 전체 수열

STL을 사용하지 않고 푸는 것이 목적이였기 때문에, 직접 next_premutation을 구현하였다.

생각보다 까다로운 것, 다음에 기억할 수 있을까?

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

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입력 1

3

예제 출력 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include<iostream>
 
using namespace std;
 
bool next_permutation(int *a, int n){
    int i = n-1;                    // 뒤부터 시작 
    while(i > 0 && a[i] <= a[i-1])    // 어디까지가 감소수열인가?? 
        i -= 1;
    if(i <= 0)                        // 전체가 감소수열이다. 
        return false;                // 다음 수열은 존재하지 않는다.
    int j = n-1;
    while(a[i-1] >= a[j])            // i-1보다 작거나 같은 뒤에 있는 수 찾기  
        j -= 1;            
    swap(a[i-1],a[j]);                // 찾은 수의 바로 앞 swap i-1 
    j = n - 1;                        // j는 마지막 
    while(i < j){                    // i-1 이후로, swap해줌 
        swap(a[i],a[j]);
        i +=1;
        j -=1;
    }
    return true;
}
 
int main(){
    int n;
    cin >> n;
    
    int *v = new int[n];
        
    for(int i = 0; i < n; i++)
        v[i] = i+1;
        
    do{
        for(int i = 0; i < n; i++)
            cout << v[i] << ' ';
        cout << '\n';
    }while(next_permutation(v,n));
    
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.