백준 10972,10973,10974 수열 구하기 문제

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

10972번: 다음 순열

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

10973번: 이전 순열

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

10974번: 모든 순열

다 똑같은 문제라서 한꺼번에 글을 썼다.

이런 문제 유형은 순열 문제인데, 순열을 구하는 함수는 두 가지가 있다.

• <algorithm>헤더파일의 next_permutation(v.begin(), v.end())
• <algorithm>헤더파일의 prev_permutation(v.begin(), v.end())

이 두 함수는 문자 그대로 다음 순열을 구하는 것과 그 이전 순열을 구하는 것인데,

놀랍게도 이 함수들의 반환형은 boolean 값이라 그 다음 순열 또는 그 이전 순열이 없으면 false를 반환한다.

따라서 do~while문으로 while문 안에 이 함수들을 집어넣고 false가 나올때까지 반복시키면 모든 순열을 구할 수 있게된다. (참고로, next_permutation 함수는 미리 오름차순으로 정렬, prev_permutation 함수는 미리 내림차순으로 정렬된 상태여야한다.)

 

10972번 소스 코드 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    int n; scanf("%d", &n);
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int temp; scanf("%d", &temp);
        v.push_back(temp);
    }
    if (next_permutation(v.begin(), v.end())) {
        for (int i = 0; i < n; i++) {
            printf("%d ", v[i]);
        }
    }
    else printf("-1");
    return 0;
}

10973번 소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    int n; scanf("%d", &n);
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int temp; scanf("%d", &temp);
        v.push_back(temp);
    }
    if (prev_permutation(v.begin(), v.end())) {
        for (int i = 0; i < n; i++) {
            printf("%d ", v[i]);
        }
    }
    else printf("-1");
    return 0;
}

10974번 소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    int n; scanf("%d", &n);
    vector<int> v;
    for (int i = 1; i < n+1; i++) {
        v.push_back(i);
    }
    do {
        for (int i = 0; i < n; i++) {
            printf("%d ", v[i]);
        }
        printf("\n");
    } while (next_permutation(v.begin(), v.end()));
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~