노드의 가중치가 문자열로 주어진 이진 트리가 있다고 가정해 보겠습니다. 이때 목표는 가중치 문자열에 모음(a, e, i, o, u)이 하나라도 포함된 노드의 개수를 구하는 것입니다. 예를 들어 어떤 노드의 가중치가 'aer'이라면 'a'와 'e'라는 모음이 포함되어 있으므로, 이 노드는 개수에 포함됩니다.
예제 1
입력
값을 입력한 후 생성되는 트리는 아래와 같습니다.
출력
모음이 포함된 문자열 가중치를 가진 트리 노드의 개수: 5
설명
각 트리 노드와 노드에 연결된 문자열 가중치가 주어집니다. 이제 각 노드의 문자열에 모음이 포함되어 있는지 확인합니다.
| 노드 | 가중치 | 모음 | 포함 여부 |
|---|---|---|---|
| 2 | ae | e | yes |
| 1 | bcd | 모음 없음 | no |
| 4 | io | i, o | yes |
| 3 | gfe | e | yes |
| 8 | tptpa | a | yes |
| 9 | iou | i, o, u | yes |
예제 2
입력
값을 입력한 후 생성되는 트리는 아래와 같습니다.
출력
모음이 포함된 문자열 가중치를 가진 트리 노드의 개수: 3
설명
각 트리 노드와 노드에 연결된 문자열 가중치가 주어집니다. 이제 각 노드의 문자열에 모음이 포함되어 있는지 확인합니다.
| 노드 | 가중치 | 모음 | 포함 여부 |
|---|---|---|---|
| 2 | oaei | o, a, e, i | yes |
| 1 | abcd | 모음 없음 | no |
| 4 | iio | i, o | yes |
| 3 | ggff | 모음 없음 | no |
| 8 | aaa | a | yes |
프로그램에서 사용하는 접근 방식
이 접근 방식에서는 트리 그래프에 DFS(깊이 우선 탐색)를 적용해 트리를 순회하면서, 각 노드의 가중치 문자열에 모음이 포함되어 있는지 확인합니다. 이를 위해 두 개의 벡터 Node_Weight(100)와 edge_graph[100]를 사용합니다.
- Node_Weight[] 배열을 각 노드의 가중치로 초기화합니다.
- 벡터 edge_graph를 이용해 트리를 생성합니다.
- 전역 변수 vowel을 선언하고 0으로 초기화합니다.
- check(string check_it) 함수는 문자열을 받아 모음이 포함되어 있으면 true를 반환합니다.
- length = check_it.length()로 문자열의 길이(문자 수)를 구합니다.
- for 루프를 사용해 인덱스 i=0부터 i<length까지 check_it을 순회합니다.
- 각 문자 check_it[i]를 소문자로 변환한 뒤 c에 저장합니다.
- c가 모음('a', 'e', 'i', 'o', 'u') 중 하나와 같으면 true를 반환하고, 끝까지 모음이 없으면 false를 반환합니다.
- string_vowel(int node, int root) 함수는 노드와 루트 노드를 인자로 받아, 주어진 트리에서 가중치에 모음이 포함된 노드의 개수를 반환합니다.
- str = Node_Weight[node]로 현재 노드의 가중치를 가져옵니다.
- check(str)이 true를 반환하면 vowel을 1 증가시킵니다.
- for 루프로 벡터 edge_graph[node]를 순회하며 트리를 탐색합니다.
- 벡터의 다음 노드에 대해 string_vowel(it, node)를 재귀적으로 호출합니다.
- 모든 함수 호출이 종료되면 vowel에는 가중치에 모음이 포함된 노드의 총 개수가 저장됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
vector<string> Node_Weight(100);
vector<int> edge_graph[100];
int vowel = 0;
bool check(string check_it){
int length = check_it.length();
for(int i = 0; i <length; i++){
char c = tolower(check_it[i]);
if(c == 'a' ||c == 'e' ||c == 'i' ||c == 'o' ||c == 'u'){
return true;
}
}
return false;
}
void string_vowel(int node, int root){
string str = Node_Weight[node];
if(check(str)){
vowel++;
}
for (int it : edge_graph[node]){
if(it == root){
continue;
}
string_vowel(it, node);
}
}
int main(){
//노드의 가중치
Node_Weight[2] = "ae";
Node_Weight[1] = "bcd";
Node_Weight[4] = "io";
Node_Weight[3] = "gfe";
Node_Weight[8] = "tptpa";
Node_Weight[9] = "iou";
//그래프 간선 생성
edge_graph[2].push_back(1);
edge_graph[2].push_back(4);
edge_graph[4].push_back(3);
edge_graph[4].push_back(8);
edge_graph[8].push_back(9);
string_vowel(2, 2);
cout<<"모음이 포함된 문자열 가중치를 가진 트리 노드의 개수: "<<vowel;
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
모음이 포함된 문자열 가중치를 가진 트리 노드의 개수: 5