백준 - 암호 만들기) 복습을 위해 작성하는 글 2023-12-25

📘 백준 - 암호 만들기

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

📝 구현

// C++
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int l;
int c;
const string VOWELS = "aeiou";

void generateStringPermutation(string& words, int depth, string& letter) {
	int consonantsCount = 0;
	int vowelsCount = 0;
    
	if (depth == l)
	{
		for (char word : letter)
		{
			if (VOWELS.find(word) != string::npos)
				++vowelsCount;
			else
				++consonantsCount;
		}
        
		if (vowelsCount >= 1 && consonantsCount >= 2)
		{
			cout << letter << '\n';
		}
        
		return;
	}
    
	for (int i = depth; i < c; ++i) {
		letter[depth] = words[i];
        
        // 값이 들어올 때 오름차순이 유지되는지 검사
		if (depth > 0 && letter[depth - 1] >= letter[depth]) {
			continue;
		}
		generateStringPermutation(words, depth + 1, letter);
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
    
	cin >> l >> c;
	string words;
	words.resize(c);
    
	for (char& word : words) {
		cin >> word;
	}
    
	sort(words.begin(), words.end());
	string letter(l, ' ');
	generateStringPermutation(words, 0, letter);
    
	return 0;
}

👨‍💻 구현 설명

• 순열 알고리즘을 기반으로 완전 탐색(브루트 포스)을 하지만, 탐색의 유망성이 없다면 탐색을 바로 종료하고 다음 탐색을 시작한다. (백트레킹)

	for (int i = depth; i < c; ++i) {
		letter[depth] = words[i];
        
        // 값이 들어올 때 오름차순이 유지되는지 검사
		if (depth > 0 && letter[depth - 1] >= letter[depth]) {
			continue;
		}
		generateStringPermutation(words, depth + 1, letter);
	}

• 위 for 문은 처음 반복에서는 words에 있는 문자들을 letter로 옮겨지는 작업만 진행된다.
• 이후 함수가 반환되고 for 문이 진행하며 i를 증가시키게 된다.
• depth는 재귀 호출될 때 +1이 돼서 넘어왔기 때문에 반환이 되고 난 depth의 값은 1이 줄어들어 있음을 기억하자
• 때문에 depth는 letter의 마지막 index이고, i는 그보다 큰 인덱스일 것이다.
• 그리고 다시 재귀호출 될 때, depth가 l과 같고 조건에 부합한다면 출력하고 아니면 그냥 반환될 것이다.
• 위와 같이 백트레킹 기법을 통해 정답을 도출해 낼 수 있다.
  
  

🙄 Thinking...

• 사실 처음에는 순열 관련 함수를 사용하는 것에 가능성을 두었지만, 조건들을 보았을 때 순열 관련 함수를 사용하여 순열을 조합한 뒤에 조건을 검사한다면 시간초과가 날 것이 분명했다.
• 그래서 오름차순 조건만큼은 순열이 만들어지는 과정에서 검사하고 오름차순이 아닐 경우에는 탐색 유망성이 없는 것이기에 탐색을 그만두는 'Backtracking' 방식으로 구현하였다.