백준 1759번 암호 만들기

문제 링크입니다: https://www.acmicpc.net/problem/1759

C와 L의 범위가 작기 때문에 브루트 포스(Brute Force)로 풀 수 있었던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 알파벳을 입력받고 모음과 자음으로 나눕니다.

2.  재귀 함수 호출을 이용해 모든 조합을 시도하는데 만들어진 문자열의 길이가 L이고 모음이 적어도 하나 있고 자음이 적어도 두개가 있으며 사전순으로 정렬했을 때 아직 result 벡터에 넣지 않은 문자열일 경우에만 result 벡터에 추가합니다.

3. result 벡터를 사전순으로 정렬하고 출력해줍니다.

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <map>

using namespace std;

 

const int MAX = 15;

 

int L, C;

char alphabet[MAX];

vector<char> vowel; //모음

vector<char> consonant; //자음

vector<string> result; //결과

map<string, bool> visited;

 

void password(int idx1, int idx2, int vCnt, int cCnt, string s)

{

        //조건 만족

        if (s.length() == L && vCnt >= 1 && cCnt >= 2)

        {

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

                 if (!visited.count(s))

                 {

                         visited[s] = true;

                         result.push_back(s);

                 }

                 return;

        }

        //기저 사례

        if (s.length() == L)

                 return;

 

        for(int i=idx1 + 1; i<vowel.size(); i++)

                 password(i, idx2, vCnt + 1, cCnt, s + vowel[i]);

        for(int i=idx2+1; i<consonant.size(); i++)

                 password(idx1, i, vCnt, cCnt + 1, s + consonant[i]);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> L >> C;

       

        for (int i = 0; i < C; i++)

        {

                 cin >> alphabet[i];

                 if (alphabet[i] == 'a' || alphabet[i] == 'e' || alphabet[i] == 'i' || alphabet[i] == 'o' || alphabet[i] == 'u')

                         vowel.push_back(alphabet[i]);

                 else

                         consonant.push_back(alphabet[i]);

        }

 

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

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

 

        password(-1, -1, 0, 0, "");

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

        for (int i = 0; i < result.size(); i++)

                 cout << result[i] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~