암호 만들기 1759

문제

접근 방법

하나씩 확인해가며 선택할지 안 할지를 결정하는 문제라고 봤다. 큐를 활용하여 그 경우를 확인해주면 될 것 같았다.

코드

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

struct word
{
    int index;     // 인덱스
    string word;   // 암호
    int vowel;     // 모음
    int consonant; // 자음
};
bool isVowel(char c) // 모음인지 확인해주는 함수
{
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    {
        return true;
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<char> cV;
    vector<string> answer;
    queue<word> q;
    int L, C;
    cin >> L >> C;
    for (int i = 0; i < C; ++i)
    {
        char c;
        cin >> c;
        cV.push_back(c);
    }
    sort(cV.begin(), cV.end());
    q.push({0, "", 0, 0});
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        if (cur.index > C)
            continue;
        if (cur.word.length() == L && cur.vowel && cur.consonant >= 2)
        {
            answer.push_back(cur.word);
            continue;
        }
        q.push({cur.index + 1, cur.word, cur.vowel, cur.consonant});
        if (isVowel(cV[cur.index])) // 모음인지 확인
            cur.vowel += 1;
        else // 자음인 경우
            cur.consonant += 1;
        q.push({cur.index + 1, cur.word + cV[cur.index], cur.vowel, cur.consonant});
    }
    sort(answer.begin(), answer.end());
    for (string a : answer)
    {
        cout << a << '\n';
    }
    return 0;
}

풀이

소문자들을 받아서 정렬해야 한다. 그래야 순서대로 선택할 수 있다.
구조체를 활용해서 인덱스, 암호, 모음, 자음을 기록해주었다.
인덱스를 증가시키며 암호에 알파벳을 넣어주거나 안 넣어주는 식으로 진행했다. 암호의 길이가 요구된 길이만큼 길고 모음이 존재하며, 자음이 2개 이상일 경우 출력할 목록에 저장해두었다.

이 문제에서 주의할 점은 조건을 확인하는 것 같다. 모음 1개, 자음 2개가 최소로 들어가야 하는 것을 놓쳤었다.
다른 사람들의 풀이를 보니 모음, 자음을 굳이 암호에 넣을 때마다 기록할 필요가 없고 마지막에 확인해주는 것이 더 효율적인 것 같다. 그리고 백 트래킹 방식으로 해야 마지막에 답안을 정렬해주는 일도 줄어드는 것 같다.