[C++] 백준 N과 M (9)

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

15663번: N과 M (9)

풀이

N과 M이 주어졌을 때,  N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제입니다. 단, 중복된 조합을 출력해서는 안되며, 오름차순 출력해야 합니다.

 

입력 받은 자연수 N개를 오름차순 정렬한 후, 재귀를 사용해 모든 조합을 만들면서 이미 만들어진 조합은 해쉬를 사용해 판단하는 방식으로 알고리즘을 구현했습니다.

 

입력 받은 N개의 자연수를 담기위한 변수 vector<int> v 와, 만들어진 조합을 해싱하기 위한 변수 map<vector<int>, int> h를 선언해줍니다. 다음으로, 현재 조합을 담기 위한 변수 vector<int> p와, 이미 사용한 수인지 판단하기 위한 변수 vector<int> visited 를 선언해줍니다.

 

permutation 함수는 현재 만들고 있는 조합 permute, 이미 사용한 숫자인지 판단하기 위한 vistied, 채워야 하는 수 n, 현재 인덱스 idx를 매개변수로 가집니다.

 

현재 숫자를 permute에 추가하고 방문처리를 해줍니다. 이 후, 종료조건을 선언해주고 이미 있는 조합이 아니라면 조건에 맞게 출력해줍니다. 

조합이 아직 만들어지지 않은 경우, 아직 사용하지 않은 숫자 (visited[i] == 0)에 대해서 재귀적으로 permutation함수를 호출해줍니다.

 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> v; 
map<vector<int>, int> h;

void permutation(vector<int> permute, vector<int> visited, int n, int idx)
{
    permute.push_back(v[idx]);
    visited[idx] = 1;
    
    // end condition
    if (permute.size() == n) {
        if (!h[permute]) {
            for (auto i : permute) {
                cout << i << " ";
            }
            cout << endl;
            h[permute] = 1;
        }
        return;
    }
	
    for (int i = 0; i < v.size(); i++) {
    	// 사용하지 않은 수에 대해서만 
        if (visited[i] == 0)
            permutation(permute, visited, n, i);
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    int num;
    vector<int> visited(n, 0); 

    for (int i = 0; i < n; i++) {
        cin >> num; 
        v.push_back(num);
    }

    sort(v.begin(), v.end());
    vector<int> p;
    for (int i = 0; i < v.size(); i++) {
        permutation(p, visited, m, i);
        p.clear();
        for (int k = 0; k < visited.size(); k++) {
            visited[k] = 0;
        }
    }
    
    return 0;
}