[백준 1759] 암호 만들기 (C++/Python)

1. 입력
- L, C (C개 중 L개 뽑기)
- 공백으로 문자 주어짐

2. 출력
- L개의 문자로 이루어진 암호 출력

3. 조건
- 모음 (a, e, i , o, u) 1개 이상
- 자음 2개 이상

4. 알고리즘

- 조합으로 풀면 된다.

 

---

 

C++)

- next_permutatoin

#include <iostream>
#include <algorithm> // sort, next_permutation
#include <vector>
#include <string>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int l, c;
    cin >> l >> c;

    vector<char> code;
    vector<int> temp;

    // 문자 입력받기
    char ch;
    for (int i = 0; i < c; i++) {
        cin >> ch;
        code.push_back(ch);
        temp.push_back((i < l) ? 0 : 1);	// 조합을 위해 확인
    }

    // 오름차순이어야하니까 정렬
    sort(code.begin(), code.end());

    int cnt1 = 0; // 모음
    int cnt2 = 0; // 자음

    do {
        string str = "";
        cnt1 = 0;
        cnt2 = 0;

        for (int i = 0; i < c; i++) {
            if (temp[i] == 0) {
                str += code[i];

                if (code[i] == 'a' || code[i] == 'e' || code[i] == 'i' || code[i] == 'o' || code[i] == 'u')
                    cnt1++;
                else
                    cnt2++;
            }
        }
        // 모음 최소 1개 이상, 자음 최소 2개 이상 포함되어 있으면 암호로 사용할 수 있다
        if (cnt1 >= 1 && cnt2 >= 2)
            cout << str << "\n";
    } while (next_permutation(temp.begin(), temp.end()));

    return 0;
}

 

- dfs

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define MAX_NUM 17
using namespace std;

int l, c;
vector<string> ans;
char arr[MAX_NUM];

// 현재까지 만든 문자열, 시작 위치, 모음, 자음
void dfs(string str, int idx, int cnt1, int cnt2) {
	if (str.length() == l) {
		if (cnt1 >= 1 && cnt2 >= 2)
			ans.push_back(str);
		return;
	}

	for (int i = idx; i < c; i++) {
		if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
			dfs(str + arr[i], i + 1, cnt1 + 1, cnt2);
		else
			dfs(str + arr[i], i + 1, cnt1, cnt2 + 1);
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> l >> c;

	for (int i = 0; i < c; i++) 
		cin >> arr[i];

	sort(arr, arr + c);

	dfs("", 0, 0, 0);
	
	for (auto str : ans)
		cout << str << "\n";

	return 0;
}

 

 

Python)

- 백트래킹

import sys

read = sys.stdin.readline

l, c = map(int, read().rstrip().split())
arr = list(read().rstrip().split())
arr = sorted(arr)

ans = [0]*l

def is_password():
    cnt_1 = 0   # 모음
    cnt_2 = 0   # 자음

    for ch in ans:
        if ch in ['a', 'e', 'i', 'o', 'u']:
            cnt_1 += 1
        else :
            cnt_2 += 1

    if cnt_1 >= 1 and cnt_2 >= 2:
        return True
    else :
        return False

def func(cnt, idx):
    if cnt == l:
        if is_password():
            print(''.join(ans))
        return
    
    for i in range(idx, c):
        ans[cnt] = arr[i]
        func(cnt+1, i+1)

func(0, 0)