백준 15663 N과 M(9) - C++

전체적인 흐름

주어진 N에 대해서 입력 받은 배열을 오름차순으로 정렬한다.(사전 순으로 증가하는 순서로 출력하기 위해)

N개 있는 배열에서 M개를 뽑아 만들 수 있는 경우의 수를 모두 구한다.

여기서 이전에 사용한 수는 사용하면 안되며 똑같은 수열을 만드는 경우는 피해야 한다.

 

예제

만약 1 1 3 4 5 라는 입력이 있다고 했을 때

이번 문제에서 요구하는 출력은

1 1

1 3

1 4

1 5

3 1

3 4

3 5

4 1

4 3

4 5

5 1

5 3

5 4

이다.

배열 인덱스 0과 1에서 1 1이 존재하는데 경우의 수를 구하다 보면 1 1이 나오고 또 1 1이 나오는데

두 개는 같은 의미이므로 같은 수열이 나온다면 하나만 출력해주면 된다.

 

풀이

그래서 이것을 똑같은 수열이 나오는지 어떻게 판별할 것인가를 고민해 봤는데 map을 사용하였다.

이전에 똑같은 수열이 나왔는지 확인하기 위해 hashMap도 생각해 봤지만 메모리를 너무 사용할거 같아 map으로 결정했다.

 

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
// 수열을 저장할 arr, N개의 수를 저장할 nums, 앞에서 사용한 수인지 확인하는 used 선언
int arr[10], nums[10], used[10];
// m = { '11':1}와 같은 식으로 저장된다. key에 수열이 나온다.
map<string,int> m;
// idx는 M개를 뽑을 때 현재까지 몇개 뽑았는지 확인하는 변수,
// str은 이전에 사용되었던 수를 가져온다 
void re(int idx,string str, int N, int M){
    if(idx == M){
        for(int k=0; k<M; k++){
            cout << arr[k] << ' ';
        }
        cout << '\n';
        return;
    } 
    
    for(int i=0; i<N; i++){
    	// 이전에 만든 수에서 현재 수를 더해 수열을 만든다. 더한다는 것은 string에서의 더하기 "a"+"b"== "ab";
        string newStr = str+to_string(nums[i]);
        // 현재 수열이 이미 사용되었는지 map에서 확인 혹은 이전에 사용된 수인지 확인 
        if(m.count(newStr) == 1 || used[i] == true) continue;
        m.insert(make_pair(newStr,1));
        arr[idx] = nums[i]; 
        used[i] = true;
        re(idx+1, newStr, N, M);
        used[i] = false;
    }
    return;
}

int main(){
    int N, M;
    cin >> N >> M;
    for(int i=0; i<N; i++){
        cin >> nums[i];
    }
    sort(nums, nums+N);
    re(0,"",N,M);
    return 0;
}