단어를 찾아 지우거나, 치환하는 알고리즘

아래 문제를 보면서 이 알고리즘을 알게되었고, 알아두면 좋은 알고리즘인 것 같아 포스팅을 하려한다.

[2941번] 크로아티아 알파벳 :: http://www.crocus.co.kr/803

사실 위의 문제는 어떻게든 풀 수 있다.(여러가지 방법으로 풀 수 있다는 의미이다.)

하지만 String STL의 다양한 함수를 이용하여 이 문제를 해결하면 좀더 고급스러운 코드를 만들 수 있는 것 같다.

위의 문제의 코드를 기반으로 알고리즘을 알아보자.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream> #include <cstdio> #include <string>   using namespace std;   string str; int main()  {     cin >> str;     int pos = 0;       string croatia[8] = { "c=","c-","dz=","d-","lj","nj","s=","z=" };     string tmp;     string star = "*";       for (int i = 0; i < 8; i++)      {         tmp = croatia[i];           if (str.find(tmp) != string::npos)          {             while ((pos = str.find(tmp)) != string::npos)              {                 str.erase(pos, tmp.length());                 str.insert(pos, star);             }         }     }       cout << str.size() << endl;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

이 코드에서 가장 중점적으로 볼 부분은 당연히 for문속의 if부분과 while부분이다.

 if (str.find(tmp) != string::npos) 
{
     while ((pos = str.find(tmp)) != string::npos) 
    {
         str.erase(pos, tmp.length());
         str.insert(pos, star);
     }
}

이 부분은 매우 재미있는 부분이다.

npos

string::find는 찾는 문자열의 첫번째 인덱스를 반환한다. 이때 찾는 문자열이 없을 경우 string::npos를 반환한다.

즉, 예외처리를 위해 nullptr처럼 string에도 find를 이용하면 npos를 이용해야 한다.

이렇게 이제 if문에 대한 해석은 :: tmp의 값을 찾아봐라. 있다면 if문속으로 없다면 npos를 반환(npos 반환값이 -1이라고 알고 있다.)

이제 아래의 while문을 보면 위의 if문과 같은데, 이제 tmp값이 있다면 그 값의 위치를 pos에 담게 된다.

아래의 erase를 통해 그 단어를 찾아 지울 수도 있고,

그 지운 부분에 다른 단어(찾아 바꾸기 기능)을 넣고 싶다면 insert를 통해 원하는 값을 넣을 수 있다.

알고리즘이 간단하지만, Java에만 존재하는 replaceAll같은 메소드를 대체 할 수 있는 좋은 알고리즘이다.