C++로 문자열에서 가장 먼저 반복되는 단어 찾기

문제 개요

이 문제에서는 공백으로 구분된 여러 단어로 이루어진 문자열 str이 주어지며, 우리의 목표는 문자열에서 가장 먼저 반복되는 단어를 찾는 것입니다.
여기서 말하는 '단어'란 두 공백 사이에 있는 문자열을 의미하며, 문자열 안에서 두 번 이상 등장하는 첫 번째 단어를 찾아야 합니다.

예제로 이해하기

입력 : str = "C program are easy to program"
출력 : program

위 예제에서는 'program'이라는 단어가 두 번 등장하므로, 결과값은 'program'이 됩니다.

해결 접근 방법

이 문제의 가장 간단한 해결책은 해시맵(hashmap) 자료구조를 활용하는 것입니다. 문자열을 단어별로 분리한 뒤, 각 단어와 해당 단어가 등장한 횟수를 해시맵에 저장합니다. 이 과정에서 현재 단어가 이미 해시맵에 존재하는지 계속 확인하며 등장 횟수를 갱신합니다.

모든 단어의 등장 횟수를 기록한 후에는 문자열을 다시 처음부터 순회하면서, 해시맵에서 등장 횟수가 1보다 큰 첫 번째 단어를 찾아 출력하면 됩니다.

팁: 성능을 더 높이려면 첫 번째 순회 과정에서 이미 해시맵에 존재하는 단어를 만나는 즉시 그 단어를 반환하면 됩니다. 이렇게 하면 두 번째 순회 없이 한 번의 탐색만으로 답을 구할 수 있습니다.

예제 코드

아래 프로그램은 위에서 설명한 해결 방법이 실제로 어떻게 동작하는지 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
string findFirstRepeatWord(string str){
    istringstream iss(str);
    string word;
    unordered_map<string, int> wordCountMap;
    while (getline(iss, word, ' ')) {
        if (wordCountMap.find(word) != wordCountMap.end())
            wordCountMap[word]++;
        else
            wordCountMap.insert(make_pair(word, 1));
    }
    istringstream iss2(str);
    while (getline(iss2, word, ' ')) {
        int count = wordCountMap[word];
        if (count > 1) {
            return word;
        }
    }
    return "NoRepetition";
}
int main(){
    string str = "C program are easy to program";
    string repeatedWord = findFirstRepeatWord(str);
    if (repeatedWord != "NoRepetition")
        cout<<"The first repeated word is '"<<repeatedWord<<"'";
    else
        cout<<"No word is Repeated in the string";
    return 0;
}

실행 결과

The first repeated word is 'program'

코드 설명

이 프로그램은 작업을 간편하게 만들기 위해 C++의 다양한 내장 기능을 활용합니다.

• istringstream & getline: 문자열을 공백(' ')을 기준으로 손쉽게 분리하여 단어를 하나씩 얻습니다.
• unordered_map: 해시 기반 맵으로, 단어별 등장 횟수를 평균 O(1)의 시간 복잡도로 저장하고 조회할 수 있습니다.

전체 알고리즘의 시간 복잡도는 문자열 길이에 비례하는 O(n)이며, 공간 복잡도 역시 저장되는 단어의 수에 비례하여 O(n)입니다.