C++로 여러 문장에 공통으로 존재하는 단어 개수 구하기

C++에서 주어진 모든 문장에 존재하는 단어 수 세기

여러 개의 문장이 문자열 형태로 주어졌을 때, 모든 문장에 공통으로 등장하는 단어의 개수를 세는 것이 이 글의 목표입니다.

참고 – 소문자로만 구성된 단어만 고려 대상으로 합니다.

예를 들어 다음과 같은 문장들이 있다고 가정해 보겠습니다.

"I am learning C language"
"learning new things is easy"
"Kids are learning healthy habits"

세 문장 모두에 존재하는 단어는 "learning" 하나뿐입니다. 따라서 결과는 1이 됩니다.

입출력 예시

입력 – "The clothes were dry", "All the kids were playing", "Those were the best days"

출력 – 모든 문장에 존재하는 단어의 개수: 2

설명 – "the"와 "were"라는 두 단어가 세 문장 모두에 포함되어 있습니다.

입력 – "We are going to school", "If you are willing then continue", "All these are sold"

출력 – 모든 문장에 존재하는 단어의 개수: 1

설명 – "are"라는 단어가 세 문장 모두에 포함되어 있습니다.

알고리즘 접근 방식

이 접근 방식에서는 먼저 첫 번째 문장의 단어들을 vector<pair<string, bool>> 타입의 set에 저장합니다. 그런 다음 unordered_map<string, bool> 타입의 check 맵을 사용하여 나머지 문장들에서 해당 단어들이 계속 등장하는지 확인합니다.

vector<string> 타입의 vec를 선언하고 문장 문자열들로 초기화합니다.
문장의 개수는 vec.size()로 구할 수 있습니다.
words_sentences(vector<string> vec, int size) 함수는 문장 벡터와 크기를 받아 모든 문장에 존재하는 단어의 개수를 반환합니다.
초기 카운트(count)를 0으로 설정합니다.
임시 문자열 str을 선언하여 문장 내 개별 단어를 저장합니다.
while 루프를 사용해 vec[0]에 저장된 첫 번째 문장을 순회합니다.
내부의 또 다른 while 루프에서 공백을 만날 때까지 문자를 하나씩 읽어 str에 단어를 추출합니다.
str에 첫 번째 문장의 단어가 담기면 (str, true) 쌍을 만들어 set에 추가합니다.
vec[0]의 모든 단어에 대해 이 과정을 반복하면, set에는 첫 번째 문장의 모든 단어가 true 값과 함께 저장됩니다.
j=1부터 j<size까지 for 루프를 사용해 두 번째 문장부터 마지막 문장까지 순회합니다.
현재 문장 vec[j]에서 각 단어를 추출해 str에 저장합니다.
check[str] = true로 설정하여 해당 단어를 check 맵에 표시합니다.
현재 문장의 모든 단어에 대해 이 과정을 반복합니다.
for 루프로 set을 순회하며, 현재 문장의 check 맵에 있는 단어들이 set에도 존재하는지 확인합니다.
다시 for 루프로 set을 순회합니다.
현재 단어가 모든 문장에 나타난다면 set[k].second가 true입니다. 이 경우 count를 증가시킵니다.
최종적으로 count 변수에는 모든 문장에 등장하는 단어의 개수가 담깁니다.
count를 결과로 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int words_sentences(vector<string> vec, int size){
    int count = 0;
    int i = 0;
    string str;
    unordered_map<string, bool> check;
    vector<pair<string, bool>> set ;
    pair<string, bool> str_bool;
    while (i < vec[0].size()){
        str = "";
        while (i < vec[0].size() && vec[0][i] != ' '){
            str += vec[0][i];
            i++;
        }
        i++;
        if (str != ""){
            str_bool = make_pair(str, true);
            set.push_back(str_bool);
        }
    }
    for (int j = 1; j < size; j++){
        check.clear();
        i = 0;
        while (i < vec[j].size()){
            str = "";
            while (i < vec[j].size() && vec[j][i] != ' '){
                str += vec[j][i];
                i++;
            }
            i++;
            if (str != ""){
                check[str] = true;
            }
        }
        for(int k = 0; k < set.size(); k++){
            if (set[k].second != false && check[set[k].first] == false){
                set[k].second = false;
            }
            else if (set[k].second != false && check[set[k].first] == true){
                check[set[k].first] = false;
            }
        }
    }
    for (int k = 0; k < set.size(); k++){
        if (set[k].second == true){
            count++;
        }
    }
    return count;
}
int main(){
    vector<string> vec;
    vec.push_back("Honesty is the best policy");
    vec.push_back("policy varies from company to company");
    vec.push_back("Employee should follow the policy of a company");
    int size = vec.size();
    cout<<"Count of words that are present in all the given sentences are: "<<words_sentences(vec, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of words that are present in all the given sentences are: 1

결과 분석

위 예제에서 "Honesty is the best policy", "policy varies from company to company", "Employee should follow the policy of a company" 세 문장 모두에 "policy"라는 단어가 등장하므로 결과는 1이 됩니다.

이 알고리즘은 각 문장의 단어를 한 번씩 추출하고, set의 크기만큼 비교를 수행하므로 시간 복잡도는 대략 O(전체 문장 길이 + 문장 수 × set 크기)입니다. 공백 기준으로 단어를 직접 파싱하므로 별도의 스트림 라이브러리 없이도 동작한다는 점이 특징입니다.