💡 백트래킹/브루트포스 알고리즘/조합론/수학
Memory 2028KB Time 0ms Code Length 944B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int L, C;
char arr[15];
struct cmp {
bool operator()(string b, string a) {
if (a < b) return true;
return false;
}
};
priority_queue<string, vector<string>, cmp> q;
int cntAIEOU(string c) {
int cnt = 0;
int csize = c.size();
for (int i = 0; i < csize; i++) {
if (c[i] == 'a' || c[i] == 'i' || c[i] == 'e' || c[i] == 'o' || c[i] == 'u') cnt++;
}
return cnt;
}
void dfs(int index, string ch) {
if (index == C) {
if (ch.size() == L) {
int cnt = cntAIEOU(ch);
if (cnt >= 1 && L - cnt >= 2) {
sort(ch.begin(), ch.end());
ch[L] = '\0';
q.push(ch);
}
}
return;
}
dfs(index + 1, ch + arr[index]);
dfs(index + 1, ch);
}
int main()
{
scanf("%d %d", &L, &C);
for (int i = 0; i < C; i++) {
scanf(" %c", &arr[i]);
}
dfs(0,"");
while (!q.empty()) {
string a = q.top(); q.pop();
printf("%s\n",a.c_str());
}
}
이 코드는 주어진 문자들(arr)로 가능한 모든 조합을 생성하고, 그 중에서 특정 조건을 만족하는 경우를 우선순위 큐에 저장한 뒤 출력하는 프로그램이다.
우선, 입력으로 받은 L과 C는 문자열의 길이와 주어진 문자의 개수를 나타낸다. 그리고 arr 배열에는 입력으로 주어진 문자들이 저장된다.
우선순위 큐 q는 문자열을 저장하는데, cmp 구조체를 이용하여 문자열을 비교하여 정렬한다. 우선순위는 사전순으로 뒤집힌 순서이다.
cntAIEOU 함수는 주어진 문자열에서 ‘a’, ‘i’, ‘e’, ‘o’, ‘u’의 개수를 세는 함수이다.
dfs 함수는 재귀적으로 문자열을 생성하고, 주어진 조건에 맞는 문자열은 우선순위 큐에 저장한다.
마지막으로 main 함수에서 L과 C를 입력받고, dfs 함수를 호출하여 가능한 모든 조합을 생성한다. 그리고 우선순위 큐에 저장된 문자열을 출력한다.
