Koala - 7기/기초 알고리즘 스터디

[백준/c++] 10974 모든순열

Suyun 2022. 7. 31. 19:57

문제

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

문제풀이

n을 입력받으면 n!개의 줄에 걸쳐 모든 순열을 순차적으로 출력하면 된다.

반복문을 사용해야 하나..? 생각이 들었는데 뭔가 이런 문제들만을 위한 방법이 따로 있을것 같아 구글링해봤더니 역시 대표적인 문제유형 중 하나였다.

vector<int>v(n);  // 입력받은 n의 크기만큼 배열을 생성하며, 동시의 각 배열의 값을 0으로 초기화해주는 코드다.

(next_permutation(v.begin(), v.end())); // <algorithm> 헤더에 있는 함수이다. vector 즉 v의 시작과 끝을 입력받으면 순차적으로 중복을 제외하고 순열을 출력해준다. 오름차순으로 정렬된 값을 가진 컨테이너로만 사용이 가능한다던데, 나는 아래 코드에서 딱히 sort로 오름차순 정리를 만들어주지 않아도 정상동작되었다.(이유는 아직까지 모르겠다...ㅠ) 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int>v(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.begin(), v.end()));
    return 0;
}