[백준/c++] 10947번: 모든 순열

문제 링크 - https://www.acmicpc.net/problem/10974

🌱 문제

🌱 풀이 1

• 이 문제도 다음 순열, 이전 순열 문제와 마찬가지로 두가지 방식으로 풀었다.
• 먼저 next_permutation() 을 이용한 풀이이다.
• next_permutation함수를 실행하기 전에 원본 수열도 출력해야 하므로 do_while문을 이용하였다. 마지막 수열이 되면, next_permutation값이 fasle가 되면서 while문을 빠져나와 출력이 끝나게 된다.

🌱 코드 1

//10974번: 모든순열
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> v;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=0; i<n; i++){
        v.push_back(i+1);
    }
    do{
        for(int i=0; i<n;i ++){
            cout<<v[i]<<" ";
        }
        cout<<"\n";

    }while(next_permutation(v.begin(),v.end()));



}

🌱 풀이 2

• 다음 수열을 찾는 과정을 직접 구현한 풀이이다.
• 이전 두문제와 같은 방식으로 풀었고, 함수를 거칠때마다 다음 수열로 수열이 바뀌게 되고, 더이상 다음 수열이 없을 때 반복문이 끝난다.
• 방법은 다음과 같다.

1. 어떤 index를 기점으로 마지막 수열인지 찾는다.
2. 끝 index부터 살펴보면서(==이 뜻은 index기점으로 내림차순 되어있기 때문에 가장 작은수중에서 찾는다는 말과 같다.) i-1번째 숫자보다 큰 숫자가 나오면 index j라고 한다
3. i-1 번째 수와 j번째 수를 swap한다.
4. i번째 수부터 n-1번째 수의 순서를 반대로 swap 한다.
5. 그럼 다음 수열 완성!

🌱 코드 2

//10974번: 모든 순열_re
#include <iostream>
using namespace std;
int n;
int arr[9];


bool func(int arr[],int n){
    int i=n-1;
    while(i>0 && arr[i-1]>arr[i])
    i--;


    if(i<=0)
    return false;

    int j= n-1;
    while(arr[i-1]>arr[j])
    j--;

    swap(arr[i-1],arr[j]);
    j=n-1;
    while(i<j){
        swap(arr[i],arr[j]);
        i++;
        j--;
    }
 
    return true;
}

int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        arr[i]=i+1;
    }
    do{
        for(int i=0; i<n; i++){
            cout<<arr[i]<<" ";
        }
        cout<<"\n";
    }while(func(arr,n));


}