백준 [13022] - 늑대와 올바른 단어 (c++)

백준 13022번 - 늑대와 올바른 단어(실버 2)

https://www.acmicpc.net/problem/13022

풀이

입력된 문자열이 규칙 1, 2를 충족시키는지 검사해야 한다.

규칙1: w, o, l, f 가 n 번 나온 단어는 올바른 단어(순서는 w, o, l, f 로 나와야함)

규칙2: 올바른 단어 2개를 이은 단어도 올바른 단어

 

규칙 1 을 만족시킬수 있는 단어는 wolf, wwoollff.. 등이 있다.

 

우선 문자가 반복된 횟수를 구한다. (wcnt 에 저장)

문자가 바뀐 지점 인덱스 +1 을 저장해서 구했다.

    for (int i = 0; i < str.size(); i++)
    {
        // 문자가 변한 구간
        if (i>=1 && str[i]!= str[i-1])
        {
            wcnt = i;
            break;
        }
    }

 

이제 각 문자별로 등장횟수를 카운트한다.

저는 'f' 를 기준으로 f다음에 f를 제외한 다른 문자가 나오면

각 문자별 등장 횟수가 wcnt 와 일치 하는지 검사했습니다.

 

여기서 1번 조건을 충족시키려면 현재까지 구간의 문자열은

w x (wcnt 횟수 반복) + o x (wcnt 횟수 반복)  +  l x (wcnt 횟수 반복)  + f x (wcnt 횟수 반복) 입니다.

 

만약 현재 구간까지 문자열이 1번 조건을 충족시킨다면, 다음 구간도 검사해야겠죠.

남은 구간만 다시 문자열을 동일하게 검사하면 됩니다.

저는 replace 로 현재검사한 구간을 제거하고

아직 문자가 남아있다면 재귀시켜서 다시 검사했습니다.

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

bool isWolf(string str)
{
    int wcnt = 0;

    // 각각 문자열 카운트
    int w = 0;
    int o = 0;
    int l = 0;
    int f = 0;

    for (int i = 0; i < str.size(); i++)
    {
        // 문자가 변한 구간
        if (i>=1 && str[i]!= str[i-1])
        {
            wcnt = i;
            break;
        }
    }

    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'w')
        {
            w++;
        }
        if (str[i] == 'o')
        {
            o++;
        }
        if (str[i] == 'l')
        {
            l++;
        }
        if (str[i] == 'f')
        {
            f++;

            // f 연속 끝나면 발동
            // 문자열 인덱스에러 방지
            if (i == str.size() - 1 || (i < str.size() - 1 && str[i] != str[i + 1]))
            {
                // 모든 글자의 수가 같으면 
                if (wcnt == w && wcnt == o && wcnt == l && wcnt == f)
                {
                    string wolfstr = "wolf";
                    string findstr = "";

                    for (int j = 0; j < wolfstr.size(); j++)
                    {
                        for (int k = 0; k < wcnt; k++)
                        {
                            findstr += wolfstr[j];
                        }
                    }

                    // findstr 이 있는지 확인
                    int pos = str.find(findstr);
                    // 없으면 리턴시킴
                    if (pos== string::npos)
                    {
                        return false;
                    }
                    // 문자 제거
                    str = str.replace(str.find(findstr), findstr.length(), "");

                    if (str.size() == 0)
                    {
                        return true;
                    }
                    else
                    {
                        // 다시 문자 검사
                        return isWolf(str);
                    }
                }
                else
                {
                    return false;
                }
            }
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int result = 0;

    string str;
    cin >> str;

    cout << isWolf(str);
    return 0;
}