임의의 크기를 가진 단어 문자열 배열이 주어졌을 때, 하나의 문자열을 여러 가지 방식으로 분할하되 분할된 각 조각이 사전에 등록된 유효한 단어가 되도록 만들고, 그중 필요한 분할 횟수가 가장 적은 경우, 즉 최소 단어 분할(Minimum Word Break) 횟수를 계산하는 것이 이 문제의 목표입니다. 이 솔루션은 문자열을 효율적으로 탐색할 수 있도록 트라이(Trie) 자료구조를 활용합니다.
다양한 입력·출력 시나리오를 통해 문제를 살펴보겠습니다.
입력 − string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all"} / 분할 대상 문자열: Hellall
출력 − 최소 단어 분할 횟수: 1
설명 − 여러 개의 단어가 주어져 있습니다. 두 문자열, 즉 Hell과 all을 이어 붙인 뒤 이를 분할해 보겠습니다. Hellall은 "Hell all"로 나눌 수 있으며, 이것이 첫 번째 분할이고 두 단어 모두 사전에 존재하는 유효한 단어입니다. 여기서 더 분할해 "He ll aa"처럼 만들면 어떠한 유효한 문자열도 형성되지 않습니다. 따라서 출력은 1입니다.
입력 − string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all"} / 분할 대상 문자열: Hellwell
출력 − 최소 단어 분할 횟수: 1
설명 − 이번에는 Hell과 well을 이어 붙인 문자열을 분할합니다. Hellwell은 "Hell well"로 나눌 수 있으며, 이것이 첫 번째 분할이고 두 단어 모두 유효합니다. 추가로 "He ll well"처럼 잘라내면 유효한 문자열이 되지 않으므로 출력은 1입니다.
프로그램에서 사용하는 접근 방식
단어 문자열 배열을 입력받고 size() 함수를 사용해 배열의 크기를 계산합니다.
min_val 변수를 선언하고 가능한 최댓값인 INT_MAX로 초기화합니다.
구조체 타입의 포인터 root를 생성하고 Return_Node() 함수의 반환값으로 설정합니다.
i를 0부터 배열 크기까지 증가시키는 FOR 루프를 실행하며, 루프 안에서 Insert_Node() 함수를 호출해 트리에 노드를 삽입합니다.
Minimum_Break() 함수를 호출해 가능한 최소 단어 분할 횟수를 계산하고 최종 결과를 출력합니다.
단어를 데이터로 가지는 노드 트리를 구성하기 위한 구조체를 선언합니다.
포인터 배열 ptr[total_Alpha]와 불리언 변수 check를 생성합니다.
Return_Node(void) 함수 내부
구조체 타입의 포인터 ptr_1을 생성하고 ptr_1->check를 false로 설정합니다.
i를 0부터 total_Alpha 미만까지 증가시키는 FOR 루프를 실행하며, 루프 안에서 ptr_1->ptr[i]를 NULL로 설정합니다.
ptr_1을 반환합니다.
Insert_Node(struct node* root, string val) 함수 내부
포인터 ptr_1을 생성하고 root로 설정합니다.
i를 0부터 val.length() 미만까지 증가시키는 FOR 루프를 실행하며, 루프 안에서 key를 val[i] - 'a'로 설정한 뒤 ptr_1->ptr[key]가 NULL인지 검사하고, NULL이면 Return_Node() 함수의 호출 결과를 할당합니다.
ptr_1을 ptr_1->ptr[key]로 갱신한 후 ptr_1->check를 true로 설정합니다.
Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0) 함수 내부
포인터 ptr_1을 생성하고 root로 설정합니다.
first가 val.length()와 같은지 검사하고, 같다면 *temp에 min(*temp, a - 1)의 결과를 저장한 후 반환합니다.
i를 first부터 val 길이 미만까지 증가시키는 FOR 루프를 실행하며, 루프 안에서 address를 val[i] - 'a'로 설정하고 ptr_1->ptr[address]가 NULL이면 반환합니다.
ptr_1->ptr[address]->check가 true이면 Minimum_Break(root, val, i + 1, temp, a + 1)을 재귀 호출합니다.
ptr_1을 ptr_1->ptr[address]로 갱신합니다.
예제
#include <bits/stdc++.h>
using namespace std;
#define total_Alpha 26
//create a tree of nodes of words
struct node{
struct node* ptr[total_Alpha];
bool check;
};
//Return tree with all nodes
struct node* Return_Node(void){
struct node* ptr_1 = new node;
ptr_1->check = false;
for (int i = 0; i < total_Alpha; i++){
ptr_1->ptr[i] = NULL;
}
return ptr_1;
}
//insert values to the nodes in a tree
void Insert_Node(struct node* root, string val){
struct node* ptr_1 = root;
for(int i = 0; i < val.length(); i++){
int key = val[i] - 'a';
if(!ptr_1->ptr[key]){
ptr_1->ptr[key] = Return_Node();
}
ptr_1 = ptr_1->ptr[key];
}
ptr_1->check = true;
}
//calculate the minimum word break
void Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0){
struct node* ptr_1 = root;
if(first == val.length()){
*temp = min(*temp, a - 1);
return;
}
for(int i = first; i < val.length(); i++){
int address = val[i] - 'a';
if(!ptr_1->ptr[address]){
return;
}
if(ptr_1->ptr[address]->check){
Minimum_Break(root, val, i + 1, temp, a + 1);
}
ptr_1 = ptr_1->ptr[address];
}
}
int main(){
string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" };
int size = sizeof(word) / sizeof(word[0]);
int min_val = INT_MAX;
struct node* root = Return_Node();
for (int i = 0; i < size; i++){
Insert_Node(root, word[i]);
}
Minimum_Break(root, "Hellall", 0, &min_val, 0);
cout<<"Minimum Word Break is: "<< min_val;
return 0;
}출력
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Minimum Word Break is: 1