[C++] 백준 10974 모든 순열

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

10974번: 모든 순열

 

1. 서론

 

말 그대로 순열 문제. 여러 가지 방법을 테스트할 수 있어서 좋은 것 같다!! 근데 시간 초과 때문에 쫄았는데 그냥... printf 갈겼다.

 

2. 문제 설명

 

N이 입력으로 주어진다. 그럼 1부터 n까지의 수를 n개 뽑아서 순열로(사전순으로) 출력하면 된다.

 

하... 이쯤되면 이 코드를 외우고 있어야 하는데 매번 까먹는 나는,, 또 보고 했다능,,

+ 구현하는 거 말고 문제가 심플한 김에 next_permutation 함수도 써봤다. 

재귀로 구현하는 코드는 정렬이 안되어서 나오기 때문에 sort함수로 정렬을 한 번 거쳤고 next_permutation 함수는 정렬되어서 출력돼서 따로 과정을 거치지 않았다.

 

3. 코드 설명

 

#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

vector<vector<int>> v;

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void perm(int a[], int d, int n, int r)
{
    if (d == r)
    {
        vector<int> t;
    
        for (int i = 0; i < n; i++)
            t.push_back(a[i]);
        v.push_back(t);

        return;
    }

    for (int i = d; i < n; i++)
    {
        swap(a[d], a[i]);
        perm(a, d + 1, n, r);
        swap(a[d], a[i]);
    }
}

int main()
{
    int n, i, j;

    scanf("%d", &n);

    int a[n];

    for (i = 0; i < n; i++)
        a[i] = i + 1;
    
    perm(a, 0, n, n);

    sort(v.begin(), v.end());

    for (i = 0; i < v.size(); i++)
    {
        for (j = 0; j < n; j++)
            printf("%d ", v[i][j]);
        printf("\n");
    }
}

 

재귀로 구현되어 있는 순열 코드다... 사전 순으로 정렬이 되어있지 않아서 sort함수를 써줬다.

 

+ next_permutation

 

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int i, n;

    scanf("%d", &n);

    int a[n];

    for (i = 0; i < n; i++)
        a[i] = i + 1;
    
    do {
        for (i = 0; i < n; i++)
            printf("%d ", a[i]);
        printf("\n");
    }while(next_permutation(a, a + n));
}

 

하 세상에 이렇게 간편하고 좋을 수가... 근데 이거 메모리 많이 드나? 재귀하는 거랑 비슷하겠지? 앞으로 이거 써야지 ㅎㅎㅎㅎ

이제 안건 아닌데 뭔가 메모리 많이 들까봐 안 썼는데 써보니까 거기서 거기인 것 같다...!! (찾아보긴 귀찮다!)