[BOJ] 1759번 | 암호 만들기 (C++)

🔗문제 보러가기

1759번: 암호 만들기

 

🧑🏻‍💻풀이 과정

1. 입력에서 모음과 자음을 각각 분리하여 따로 저장합니다.
2. 아래의 조건을 충족하면서, 저장한 모음과 자음을 조합하여 길이가 L이 될 때까지 암호를 생성합니다.
   • 모음은 최소 1개 ~ 최대 L - 2개까지 암호에 포함될 수 있습니다.
   • 자음은 최소 2개 ~ 최대 L - 1개까지 암호에 포함될 수 있습니다.
3. 생성한 암호의 길이가 L이 되었다면, 암호를 오름차순으로 정렬합니다.
4. 중복을 피하기 위해, 정렬한 암호를 set 자료구조에 저장합니다.
5. 모든 경우의 수에 대해 다 조합 하였다면, 출력합니다.

 

모음과 자음이 각각 포함되어야 할 구간값이 정해져 있기 때문에, 이 부분을 암호 생성에서 추가 조건으로 걸어줘야 합니다.

 

✏️소스 코드 및 결과

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

class Decoder
{
public:
	Decoder(int L, int C);
	void FindPasswords();
	void ShowPasswords();
private:
	void FindCombination(string password, int vowelIdx, int consonantIdx, int vowelCount, int consonantCount);
private:
	const set<char> VOWEL{ 'a', 'e', 'i', 'o', 'u' };
	string _vowels;
	string _consonants;
	set<string> _answers;
	int _L;
};

Decoder::Decoder(int L, int C)
{
	_L = L;

	for (int i = 0; i < C; i++)
	{
		char alphabet;
		cin >> alphabet;

		auto FindIter = VOWEL.find(alphabet);
		FindIter == VOWEL.end() ? _consonants.push_back(alphabet) : _vowels.push_back(alphabet);
	}
}

void Decoder::ShowPasswords()
{
	for (const auto& answer : _answers)
		cout << answer << "\n";
}

void Decoder::FindCombination(string password, int vowelIdx, int consonantIdx, int vowelCount, int consonantCount)
{
	if (password.length() == _L)
	{
		sort(password.begin(), password.end());
		_answers.emplace(password);
		return;
	}

	// 모음은 최소 1개부터 최대 L-2개까지 가질 수 있음
	for (int vi = vowelIdx; vi < _vowels.size() and vowelCount < _L - 2; vi++)
	{
		password.push_back(_vowels[vi]);
		FindCombination(password, vi + 1, consonantIdx, vowelCount + 1, consonantCount);
		password.pop_back();
	}

	// 자음은 최소 2개부터 최대 L-1개까지 가질 수 있음
	for (int ci = consonantIdx; ci < _consonants.size() and consonantCount < _L - 1; ci++)
	{
		password.push_back(_consonants[ci]);
		FindCombination(password, vowelIdx, ci + 1, vowelCount, consonantCount + 1);
		password.pop_back();
	}
}

void Decoder::FindPasswords()
{
	string password = "";
	FindCombination(password, 0, 0, 0, 0);
}

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

	int L, C;
	cin >> L >> C;

	Decoder decoder(L, C);
	decoder.FindPasswords();
	decoder.ShowPasswords();
	return 0;
}

 

관리해야 할 데이터들이 많아지니, 클래스 파서 관리하는 게 역시 편하네요.