C++로 주어진 패턴으로 끝나는 문자열 개수 세기

문자열 배열 str[]과 패턴 문자열 pat이 주어졌을 때, 배열의 요소 중 패턴 pat으로 끝나는 문자열의 개수를 구하는 것이 목표입니다.

해결 방법은 간단합니다. 배열의 각 문자열을 순회하면서 뒤에서부터 문자를 하나씩 비교하고, 모두 일치하면 카운트를 증가시키면 됩니다.

예제로 이해하기

입력 1

str[] = { "kittens", "hens", "deers", "dogs" }, pat = "ens"

출력 1

주어진 패턴으로 끝나는 문자열 개수: 2

설명: "kittens"과 "hens"가 "ens"로 끝납니다.

입력 2

str[] = { "tickets", "wickets", "bats", "cricket" }, pat = "et"

출력 2

주어진 패턴으로 끝나는 문자열 개수: 1

설명: "wickets"만 "et"으로 끝납니다.

알고리즘 접근 방식

문자열 배열 str[]과 패턴 문자열 pat을 입력받습니다.
N은 배열에 있는 문자열의 개수입니다.
함수 endPattern(string str[], int n, string ptr)은 주어진 패턴으로 끝나는 문자열의 개수를 반환합니다.
초기 카운트 변수를 0으로 설정합니다.
for 반복문으로 i=0부터 i<n까지 배열의 모든 문자열을 순회합니다.
각 문자열 str[i]를 s라고 하고, slen을 s의 길이로 설정합니다.
plen은 패턴 ptr의 길이이며, flag는 1로 초기화합니다.
slen과 plen을 각각 1씩 감소시켜 문자열과 패턴의 마지막 인덱스를 얻습니다.
while 반복문으로 plen>=0인 동안 뒤에서부터 문자를 비교합니다.
비교 중 s[slen] != ptr[plen]인 경우 flag를 0으로 설정하고 반복문을 종료합니다. 일치하면 plen과 slen을 감소시켜 다음 문자를 검사합니다.
while 반복문이 끝난 후에도 flag가 1이면 해당 문자열이 패턴으로 끝나는 것이므로 count를 증가시킵니다.
모든 반복이 끝나면 count를 반환합니다. 이것이 주어진 패턴으로 끝나는 문자열의 총 개수입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int endPattern(string str[], int n, string ptr){
    int count=0;
    for(int i=0;i<n;i++){
        string s=str[i];
        int slen=s.length();
        int plen=ptr.length();
        int flag=1;
        slen--; // 마지막 인덱스
        plen--;
        while(plen>=0){
            if(ptr[plen]!=s[slen]){
                flag=0;
                break;
            }
            plen--;
            slen--;
        }
        if(flag==1)
            { count++; }
    }
    return count;
}
int main(){
    string patrn = "pes";
    int N = 4;
    string str[] = { "stripes", "cars", "ripes", "pipes" };
    cout <<"Strings that end with given pattern: "<<endPattern(str,N,patrn);
    return 0;
}

실행 결과

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

Strings that end with given pattern: 3

이 코드에서 "stripes", "ripes", "pipes" 세 문자열이 "pes"로 끝나므로 결과는 3입니다. 이 알고리즘의 시간 복잡도는 O(N × L)입니다. 여기서 N은 문자열의 개수, L은 평균 문자열 길이입니다.