1759. 암호 만들기

문제: https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 bruteforce 문제다.  알파벳이 소문자 하나씩만 unique하게 존재하기 때문에 따로 메모리를 대서 캐싱하지 않아도 된다.  알파벳이 unique하지 않은 경우 캐싱을 해줘야한다.

 예를 들면, {'a', 'a', 'b', 'c'} 같은 경우가 있을 때 0번 인덱스 'a'를 사용하고 1번 인덱스를 사용하지 않는 경우 1, 0번 인덱스를 사용하지 않고 1번 인덱스를 사용하는 경우가 있는 경우 뒤의 'b', 'c'를 사용할때 'abc'의 경우의 수가 2가지다.  결과값에 두 가지가 들어가면 안되므로 set으로 캐싱하면 unique한 결과값을 얻을 수 있다.

 본 문제의 경우는 주어진 input의 character가 unique하게 들어오므로, 메모리를 따로 대지 않아도 unique한 결과값을 얻을 수 있다.

 

#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <unordered_set>

using namespace std;

vector<char> parentChars = {'a', 'e', 'i', 'u', 'o'};

bool check(string target){
    int childCnt = 0;
    int parentCnt = 0;
    
    for(char c : target){
        auto it = find(parentChars.begin(), parentChars.end(), c);
        if(it != parentChars.end()){
            parentCnt++;
        } else {
            childCnt++;
        }
    }
    bool ret = false;
    if(parentCnt > 0 && childCnt > 1){
        ret = true;
    }
    return ret;
}

void traverse(vector<char> arr, int idx, string ans, int L){
    if(ans.size() == L && check(ans)){
        cout << ans << endl;
        return;
    }
    
    if(idx == arr.size()){
        return;
    }

    ans.push_back(arr[idx]);
    traverse(arr, idx + 1, ans, L);
    ans.pop_back();
    traverse(arr, idx + 1, ans, L);
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int L, C;
    cin >> L >> C;
    vector<char> arr;

    for(int i = 0; i < C; i++){
        char v;
        cin >> v;
        arr.push_back(v);
    }

    sort(arr.begin(), arr.end());
    
    traverse(arr, 0, {}, L);
    return 0;
}

Time complexity: O(2^n * n)

Space complexity: O(2^n)