C++로 문장 속 회문(Palindrome) 단어 개수 구하기

문제 이해하기

영어 문장이 담긴 문자열이 하나 주어집니다. 목표는 이 문장에서 회문(palindrome)에 해당하는 단어가 몇 개인지 세는 것입니다. 회문 단어란 앞에서부터 읽어도 뒤에서부터 읽어도 글자 순서가 완전히 같은 단어를 의미합니다.

예를 들어 문장이 “Madam speaks good Malayalam”이라면 회문 단어는 2개입니다(Madam, Malayalam).

참고: 단어에는 대문자와 소문자가 섞여 있을 수 있으며, 대소문자는 구분하지 않고 비교합니다.

예시

입력 − str = “My Mom and Anna left at Noon”
출력 − 문장 속 회문 단어의 개수: 3
설명 − Mom, Anna, Noon이 회문 단어입니다(대소문자 무관).

입력 − str = “I am at level 121 in Racecar game”
출력 − 문장 속 회문 단어의 개수: 4
설명 − I, level, 121, Racecar가 회문으로 판정됩니다. 한 글자짜리 단어나 숫자로 이루어진 토큰도 앞뒤가 같다면 회문으로 간주할 수 있습니다.

접근 방법

핵심 아이디어는 다음과 같습니다.

문장을 공백(“ ”)을 기준으로 한 단어씩 잘라내어 별도의 검사 함수로 전달합니다.
검사 함수는 단어의 모든 글자를 먼저 소문자로 변환한 뒤, 첫 글자와 마지막 글자(word[0] vs word[len-1]), 두 번째 글자와 끝에서 두 번째 글자(word[1] vs word[len-2])를 차례로 비교합니다.
비교 중 불일치가 발견되면 즉시 false를 반환하고, 끝까지 모두 일치하면 true를 반환합니다.

알고리즘 단계

문장을 담은 문자열 str[]을 준비합니다.
함수 check(string extra)는 전달받은 문자열이 회문이면 true, 아니면 false를 반환합니다.
문자열 길이를 len = extra.length()로 구합니다.
transform(extra.begin(), extra.end(), extra.begin(), ::tolower)으로 문자열 전체를 소문자로 변환합니다.
for 반복문으로 인덱스 0부터 i < len까지 순회하며 extra[i]와 extra[len-1]을 비교하고, 불일치 시 false를 반환합니다. 모두 일치하면 true를 반환합니다.
함수 palindrome(string str, int length)는 문장과 그 길이를 받아 회문 단어의 총 개수를 반환합니다.
초기 count를 0으로 설정합니다.
임시 문자열 extra = “”를 두어 개별 단어를 조립·저장합니다.
인덱스 0부터 i < length까지 문장을 순회합니다.
임시 문자 temp = str.at(i)에 현재 글자를 저장합니다.
temp가 공백이 아니면 extra에 추가하여 단어를 만듭니다.
temp가 공백이라면 지금까지 만든 단어에 대해 check(extra)를 호출하고, true이면 count를 1 증가시킨 뒤 extra를 다시 “”로 초기화합니다.
마지막 단어도 검사되도록 하려면 문장 끝에 공백을 하나 붙여주는 것이 좋습니다(main 함수에서 str + “ ” 처리).
최종 count가 문장 내 회문 단어의 총 개수이며, 이를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
bool check(string extra){
    int len = extra.length();
    transform(extra.begin(), extra.end(), extra.begin(), ::tolower);
    for (int i = 0; i < len; i++,len--){
        if (extra.at(i) != extra.at(len - 1)){
            return false;
        }
    }
    return true;
}
int palindrome(string str, int length){
    int count = 0;
    string extra = "";
    for (int i = 0; i < length; i++){
        char temp = str.at(i);
        if (temp != ' '){
            extra = extra + temp;
        }
        else{
            if (check(extra))
                { count++; }
            extra = "";
        }
    }
    return count;
}
int main(){
    string str = "nitin wants nitin for his company named nitin after nitin";
    str = str + " ";
    int length = str.length();
    cout<<"Count of palindrome words in a sentence are: "<<palindrome(str, length)<<endl;
    return 0;
}

실행 결과

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

Count of palindrome words in a sentence are: 4

복잡도 분석

각 단어의 회문 여부 검사는 해당 단어 길이의 절반 정도만 비교하면 되므로 O(L)이며, 문장 전체를 한 번만 순회하므로 전체 시간 복잡도는 O(N)(N은 문장의 총 길이)입니다. 추가로 사용되는 공간은 임시 단어를 저장하는 버퍼 정도로 O(L) 수준입니다.