[백준알고리즘] 1759번: 암호 만들기 -C++

[백준알고리즘] 1759번: 암호 만들기 -C++

1759번: 암호 만들기 (acmicpc.net)

1759번: 암호 만들기

예전에 파이썬으로 풀었던 문제다. 하지만, 역시나 기억이 나지 않았다. ㅋㅋ..

 

다 풀고 글을 쓰려고 예전 글을 보니까 역시 파이썬 코드는 간단하다. 오늘 짠 C++ 코드도 더 간단히 가능하겠지만, 요즘 복잡하면서 간단한 것보다는 길더라도 깔끔한 코드를 지향하고 있어서 뭐 만족한다.

 

예전에 파이썬으로 풀었던 포스팅은 아래의 링크를 통해 가면 있다.

[백준알고리즘] 1759번: 암호 만들기 -Python (tistory.com)

[백준알고리즘] 1759번: 암호 만들기 -Python

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제를 풀 때 몇 가지 고려해야 할 점이 있다.

• 암호는 L개의 서로다른 알파벳 소문자로 구성
• 최소 한 개의 모음이 포함
• 최소 두 개의 자음이 포함
• 암호 자체가 증가하는 순서로만 구성 (오름차순)
• 생성되는 여러 암호들을 오름차순으로 출력

 

여기서 세 번째 적었던 '최소 두 개의 자음이 포함'이라는 조건을 나중에 알아서 한 번 틀렸다. ㅋㅋ;

 

 

아무튼 문제를 풀 때 재귀를 사용했다. printCrypto라는 함수를 재귀적으로 호출해서 암호문이 생성되면 출력해주도록 했다. 인자로는 주어진 단어들을 오름차순으로 정렬한 벡터 dictionary와 그 벡터에서 각 문자를 가리키는 index, 그리고 암호문을 만들기 위해 필요한 단어의 개수인 step, 단계적으로 생성되는 암호문인 crypto가 있다.

 

주어진 단어에서 각 단어마다 암호문에 포함시키는 경우와 포함시키지 않는 경우로 나눠서 재귀적으로 호출한다. 주어진 암호문을 오름차순으로 정렬했기 때문에 생성되는 암호문도 오름차순으로 생성하기 위해서는 각 문자가 포함되는 경우를 먼저 확인해주어야 한다.

 

그렇게 암호문에 필요한 문자의 개수를 모두 채웠으면, 모음의 개수와 자음의 개수를 확인한 후 출력한다. 모음과 자음의 개수를 확인하는 함수는 isContainVowel 함수와 isContainConsonant 함수로 나눠서 만들어줬다.

암호문의 길이가 15인 경우가 최대이기 때문에 교집합을 구하려다가 일일이 반복문으로 각 단어들을 확인해주는 것이 빠를 것 같아서 직접 반복문을 돌렸다.

 

isContainVowel과 isContainConsonant 함수는 굳이 나누지 않아도 한 번에 확인을 할 수 있겠지만, 길어지더라도 이게 더 직관적이고 깔끔한 것 같다.. 고 위로하는 중이다.

 

아무튼 아래의 코드대로 실행을 하면 위의 조건들을 모두 만족하고 통과하게 된다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

bool isContainVowel(const std::vector<char>& text)
{
	std::set<char> vowels = { 'a', 'e', 'i', 'o', 'u' };

	for (auto t : text)
		if (vowels.find(t) != vowels.end())
			return true;
	
	return false;
}

bool isContainConsonant(const std::vector<char>& text)
{
	std::set<char> vowels = { 'a', 'e', 'i', 'o', 'u' };

	int vowelCount = 0;
	for (auto t : text)
		if (vowels.find(t) != vowels.end())
			vowelCount++;

	return (2 <= text.size() - vowelCount);
}

void printCrypto(std::vector<char>& dictionary, int index, int step, std::vector<char>& crypto)
{
	// DFS
	if (0 == step)
	{
		if (!isContainConsonant(crypto) || !isContainVowel(crypto))
			return;

		for (auto c : crypto)
			std::cout << c;
		std::cout << '\n';
		return;
	}

	if (dictionary.size() == index)
		return;

	crypto.push_back(dictionary[index]);
	printCrypto(dictionary, index + 1, step - 1, crypto);
	crypto.pop_back();
	printCrypto(dictionary, index + 1, step, crypto);
}

void solve(void)
{
	int l, c;
	std::cin >> l >> c;

	std::vector<char> dictionary(c);
	for (int i = 0; i < c; i++)
		std::cin >> dictionary[i];

	std::sort(dictionary.begin(), dictionary.end());
	std::vector<char> crypto;

	printCrypto(dictionary, 0, l, crypto);
}