[ SWEA 1213 ] String (C++)

SWEXpertAcademy의 String(1213 / d3) 문제이다.

[ 문제풀이 ]

1) 이 문제는 주어진 문자열에서, 우리가 찾고자 하는 문자열이 몇개가 나오는지 체크해줘야 하는 문제이다.

   접근하는 방법은 어렵지 않다. 모든 문자열을 탐색하면서 하나하나 모두 비교해보면 된다.

   모든 문자열의 탐색범위는 "처음 ~ 주어진 문자열의 길이 - 찾고자하는 문자열의 길이 + 1" 이 된다.

   식만 보면 엄청 복잡해 보일 수 있지만 예를 통해서 쉽게 이해해보자.

   "ABCDABCDAB" 라는 길이가 10인 문자열에서 "CD"를 찾는다고 생각해보자.

   주어진 문자열의 길이는 10이고, 찾고자 하는 문자열의 길이는 2이다. 우리가 찾고자하는 문자열의 길이가 2이기 때문에

   가장 마지막에 빨강색으로 색칠된 B에서는 탐색을 진행할 수가 없다. 왜냐하면 B뒤에는 더 이상 문자열이 없기 때문에

   2칸짜리 문자열을 찾을 수 없기 때문이다. 아마, 마지막 한 칸 앞에있는 파랑색으로 칠해진 A가 마지막으로 탐색을 하는

   문자가 될것이다. 즉, 길이가 10인(인덱싱하면 0번 ~ 9번) 문자열에서, 길이가 2인 문자열을 탐색하려면

   10 - 2 + 1 까지만 탐색을 하면 된다. 그렇게 되면 0 ~ 9까지인데 뭔가 말이 이상해보인다.

   본인이 말하고자 하는 것은 for문의 범위에 대해서 얘기를 한 것이다.

 for(int i = 0 ; i < 10 - 2 + 1; i++) = for(int i = 0 ; i < 9; i++)

 위와 같이 코드로 나타내면 0부터 9보다 작을때까지, 즉, 0 ~ 8까지만 탐색을 하게 된다.

   

   이제는 문자열을 비교만 하면된다. 어떻게 비교하는지 코드를 먼저 보고 이해해보자.

 for(int i = 0 ; i < Inp.length() - Find.length() + 1; i++)

 {

string Temp = "";

for(int j = i; j < i + Find_Len; j++) Temp = Temp + Inp[j];

if(Temp == Find) Answer++;

  }

     본인이 구현한 문자열을 찾는 방법이다.

     어느 한 점에서, 찾고자 하는 문자열의 길이만큼 문자들을 모두 더해서, 그 결과값이 찾고자 하는 문자열과 같다면 정답의

     갯수를 ++ 해주는 방식이다.

     문제 자체가 그리 어렵지 않기 때문에 천천히 생각해보면 쉽게 해결할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<string>
 
#define endl "\n"
using namespace std;
 
int Answer, Find_Len;
string Inp;
string Find;
 
void Initialize()
{
    Answer = 0;
    Inp.clear();
    Find.clear();
}
 
void Input()
{
    int Num; cin >> Num;
    cin >> Find;
    cin >> Inp;
}
 
void Solution()
{
    Find_Len = Find.length();
    for (int i = 0; i < Inp.length() - Find_Len + 1; i++)
    {
        string Temp = "";
        for (int j = i; j < i + Find_Len; j++)
        {
            Temp = Temp + Inp[j];
        }
 
        if (Temp == Find) Answer++;
    }
}
 
void Solve()
{
    int Tc = 10;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}