[Algorithm]Baekjoon 1759번 : 암호 만들기

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

1759번: 암호 만들기

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
 
using namespace std;
 
int targetCount = 0;
vector<string> answer;
map<string, bool> isVowel;
 
void solution(int index, string sum,int conCount, int vowelCount, vector<string>& input)
{
    string before = sum;
    sum += input[index];
    
    int prevVowelCount = vowelCount;
    int prevConCount = conCount;
 
    if (isVowel[input[index]]) vowelCount += 1;
    else conCount += 1;
    
    if (sum.size() == targetCount)
    {
        if (vowelCount >= 1 && conCount >= 2)
        {
            answer.push_back(sum);
        }
    }
 
    if (index + 1 <= input.size() - 1)
    {
        solution(index + 1, sum, conCount,vowelCount,input); // 자기자신 포함값
        solution(index + 1, before, prevConCount,prevVowelCount,input); // 비포함값
    }
    else return;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int l = 0;
    int c = 0;
    string input = "";
    vector<string> strings;
 
    isVowel["a"] = true;
    isVowel["e"] = true;
    isVowel["i"] = true;
    isVowel["o"] = true;
    isVowel["u"] = true;
 
    cin >> l >> c;
 
    targetCount = l;
 
    for (int i = 0; i < c; i++)
    {
        cin >> input;
        strings.push_back(input);
    }
 
    sort(strings.begin(), strings.end());
    
    solution(0, "", 0,0,strings);
    
    for (auto temp : answer)
    {
        cout << temp << endl;
    }
 
}
 

 

이전에 풀었던 백트래킹 기본예제에서 좀 더 응용한 문제다.

추가된 조건은 

 

1. 암호는 알파벳순이여야 한다.

2. 모음은 최소 1개이상, 자음은 최소 2개이상이여야 한다.

 

알파벳순이여야하기 때문에 일단 input값들에 대해 정렬을 한번 해줬고, 재귀를 돌릴 때 '자기자신을 포함한 값'을 먼저 실행하게 했다. 비포함을 먼저하면 알파벳역순으로 실행되니 주의하자.

 

모음 자음검사는 모음에대한 룩업테이블을 만들어서 해결했다. 타겟크기의 사이즈가 될 때, 모음 자음개수가 조건에 맞아야 결과벡터에 넣을수 있게 코드를 작성했다.

map의 value에 bool자료형을 선언할 경우 디폴트로 false가 셋팅되기 때문에 개수가 적은 모음에 대해서만 true를 미리 넣어놓고 검사하는 식으로 작성했다.

물론 자기자신 비포함에 대해 재귀를 돌릴때는 모음,자음 카운트도 카운팅하기전 값으로 넣어줘야한다.