1759_암호만들기 c++

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

1759번: 암호 만들기

 

빽트랙킹 . . 조합 . . . 

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

int l, c;
string s ;
bool isvisted[16];

void dfs(int cnt, int idx)
{

    if (cnt == l)
    {
        //base condition
        // 모음 하나 자음 두개 사전순
        int m = 0, j = 0;

        for (int i = 0; i < s.size(); i++)
        {
            if (visited[i])
            {
                if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
                    m++;
                else
                    j++;
            }
        }

        if (m >= 1 && j >= 2)
        {
            for (int i = 0; i < s.size(); i++)
            {
                if (visited[i])
                    cout << s[i];
            }
            cout << '\n';
        }

        return;
    }

    for (int i = idx; i < s.size(); i++)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            dfs(cnt + 1, i);
            visited[i] = false;
        }
    }
    return;
}

int main()
{
    cin >> l >> c;

    for (int i = 0; i < c; i++)
    {
        char temp;
        cin >> temp;
        s += temp;
    }
    sort(s.begin(), s.end());
    dfs(0, 0);

    return 0;
}

빽트랙킹으로 풀은거 . .  정렬을 한 번 시켜주면 dfs 돌릴 땐 정렬 신경 안 써도 된다는 점이 가슴을 참 아프게 함

 

 

이건 조합으로

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

int l, c;
vector<int > visit;
vector<char> alpa ;

int main(){

    cin >> l >> c ;

    for(int i=0; i< c; i++){
        char temp;
        cin >> temp;
        alpa.push_back(temp);
        visit.push_back(1);
    }   

    sort(alpa.begin(), alpa.end());

    for(int i=0; i< l; i++){
        visit[i] = 0;
    }

    do{
        string s  ="";
        for(int i=0; i< c; i++){
            if(visit[i] ==0)
                s+= alpa[i];
        }

        int m=0, j=0;

        for(int i=0; i< s.size(); i++){
            if(s[i] =='a'||s[i] =='e'||s[i] =='i'||s[i] =='o'||s[i] =='u') m++;
            else j++;
        }
        if(m >=1 && j>=2){
            cout << s <<'\n' ;
        }
   


    }while (next_permutation(visit.begin(), visit.end())) ;
    
    

}

 

이건 조합으로 next_permutation 참 좋다

 

성능은 둘다 비슷 ~