[백준/c++] 13022 늑대와 올바른 단어

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

13022번: 늑대와 올바른 단어

 

✨ 문제풀이

문자열 구현 문제입니다. 저는 다음과 같이 문제를 해결했습니다.

1. 문자열에서 현재 가리키는 문자가 w라면 w가 연속으로 몇 번 나오는지 센다 (count에 저장)
2. wolf가 총 네 글자이므로 4 * count 개의 문자만큼의 문자열이 올바른지 확인한다
   • count번씩 w, o, l, f 문자가 차례대로 나오는지 확인한다
3. 4*count개의 문자 다음으로 나오는 문자가 w인지 확인한다 (아니면 잘못된 문장)

 

1. 문자열에서 현재 가리키는 문자가 w라면 w가 연속으로 몇 번 나오는지 세고 count에 저장하기

int getCountOfW(int index)
{
    char letter = sentence[index];
    int count = 0;
    while (letter == 'w')
    {
        count++;
        index++;
        letter = sentence[index];
    }
    return count;
}

if (sentence[i] == 'w')
{
    count = getCountOfW(i);
}

주어진 문자열에서 w의 개수를 세기 위해 시작하는 index를 매개변수로 받고, index부터 몇 개의 w가 존재하는지 셉니다.

 

2. wolf가 총 네 글자이므로 4 * count 개의 문자만큼의 문자열이 올바른지 확인한다

(1) 4 * count개의 문자로 된 문자열 만들기

string makeCheckdSentence(int start, int end)
{
    string checkedSentence = "";
    for (int i = start; i < end; i++)
        checkedSentence += sentence[i];
    return checkedSentence;
}

string checkedSentence = makeCheckdSentence(i, i + count * 4, sentence);

원래는 substr을 사용해서 구현했는데 substr로 제가 원하는 대로 구현이 잘 안 돼서 😐 나이브하지만 for문을 이용해 구현했습니다.

 

(2) 올바른 문자열인지 확인하기

string pattern = "wolf";
int patIndex = 0;

void addPatternIndex()
{
    patIndex = (patIndex + 1) % 4;
}

bool isPattern(string str, int repetition)
{
    for (int i = 0; i < str.size(); i += repetition)
    {
        if (i > 0 && str[i] != str[i - 1])
            addPatternIndex();

        for (int r = 0; r < repetition; r++)
        {
            if (str[i + r] != pattern[patIndex])
                return false;
        }
    }
    return true;
}


if (!isPattern(checkedSentence, count))
{
    cout << "0\n";
    return 0;
}
patIndex = 0;

저는 올바른 문자열인지 확인하는 isPattern이라는 함수를 만들어주었습니다.

앞에서 몇 개의 w가 반복되는지 구한 count 와, 4*count 개의 문자로 이루어진 문자열 str이 과연 wolf라는 패턴에 맞는지 확인하는 합수입니다.

 

우리가 확인해야 하는 패턴은 wolf이므로 wolf라는 문자열을 저장한 pattern을 정의했습니다.

그리고 조건에 따라서 pattern의 인덱스를 증가해가면서 str의 문자와 pattern의 문자가 같은 문자를 가리키고 있는지 확인합니다.

pattern의 인덱스를 수정하는 경우는 다음과 같습니다.

• str의 문자를 가리키는 인덱스를 i라고 할 때, str[i]와 str[i-1]이 다를 때
  • 앞 문자는 count개 만큼 문자가 있는지 확인했고, 다음 문자에 대해서 검사해야 하므로 pattern의 문자도 다음 인덱스로 증가해줌
• 4 * count의 문자열이 올바르다고 모두 확인했고 다음 문자열을 검사해야 하므로 인덱스를 0으로 옮겨줌
  • 마지막으로 f 문자에 대해 검사해서 pattern의 인덱스가 f(3)이므로 w(0)로 옮겨줌

 

그리고 str문자열에서 count개만큼 문자가 존재하는지 확인해줍니다. 만약 적거나 많다면 pattern이 가리키는 문자와 다르게 되므로 false를 반환합니다. 따라서 이중 for문 내에서 총 count개만큼 문자를 확인했으므로 바깥에 있는 for문은 count만큼 증가해야 합니다.

 

🗓 코드

#include <iostream>
using namespace std;

string sentence;
string pattern = "wolf";
int patIndex = 0;

string makeCheckdSentence(int start, int end)
{
    string checkedSentence = "";
    for (int i = start; i < end; i++)
        checkedSentence += sentence[i];
    return checkedSentence;
}

void addPatternIndex()
{
    patIndex = (patIndex + 1) % 4;
}

bool isPattern(string str, int repetition)
{
    for (int i = 0; i < str.size(); i += repetition)
    {
        if (i > 0 && str[i] != str[i - 1])
            addPatternIndex();

        for (int r = 0; r < repetition; r++)
        {
            if (str[i + r] != pattern[patIndex])
                return false;
        }
    }
    return true;
}

int getCountOfW(int index)
{
    char letter = sentence[index];
    int count = 0;
    while (letter == 'w')
    {
        count++;
        index++;
        letter = sentence[index];
    }
    return count;
}

int main(void)
{
    cin >> sentence;

    int count = 0;
    for (int i = 0; i < sentence.size(); i += count * 4)
    {
        if (sentence[i] == 'w')
        {
            count = getCountOfW(i);
            string checkedSentence = makeCheckdSentence(i, i + count * 4);
            if (!isPattern(checkedSentence, count))
            {
                cout << "0\n";
                return 0;
            }
            patIndex = 0;
        }
        else
        {
            cout << "0\n";
            return 0;
        }
    }
    cout << "1\n";
    return 0;
}