[재귀] 암호 만들기 - 백준 1759번

1759번: 암호 만들기

여러 문자들로 문자열 경우의 수 만들기

1. 재귀 방식

void push(vector<char> arr, int index) {   
    for(int i = index; i < arr.size(); i++) {
        result += arr[i];
        push(arr, i + 1);
        result.pop_back();
    }
}

• 하나씩 계속 추가하고 꽉찼으면 pop_back()이 이루어짐

• String도 pop_back(), push_back()이 가능하다!!

2. DFS 방식

func ("", 0) {

	func("a", 1(index)) //추가한 버전
	func("", 1(index))  //안한 버전

}

Code

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

using namespace std;

int L,C;
vector<char> arr;
string result = "";

void push(vector<char> arr, int index) {
    // 결과 문자열이 L 길이에 도달한 경우 출력하고 종료
    if(result.length() == L) {
        // 모음과 자음의 개수 확인
        int vowel_count = 0, consonant_count = 0;
        for(char ch : result) {
            if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
                vowel_count++;
            else
                consonant_count++;
        }
        // 조건에 맞는 경우에만 출력
        if(vowel_count >= 1 && consonant_count >= 2)
            cout << result << "\n";
        return;
    }
    
    // 재귀 호출을 통해 조합 만들기
    for(int i = index; i < arr.size(); i++) {
        result += arr[i];
        push(arr, i + 1);
        result.pop_back(); // 이전 문자를 제거하여 다음 조합을 만들기 위해 string에도 pop_back이 있었네
    }
}

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

    cin >> L >> C;

    for(int i = 0; i < C; i++) {
        char a;
        cin >> a;
        arr.push_back(a);
    }

    sort(arr.begin(), arr.end());

    push(arr, 0);

    return 0;
}