[C++] 백준 13022: 늑대와 올바른 단어

문제

[C++] 백준 13022: 늑대와 올바른 단어 SILVER 2
https://www.acmicpc.net/problem/13022

 

---

 

접근 방법

이 문제에서 “올바른 단어”는 w^n o^n l^n f^n 꼴의 문자열이 하나 이상 이어 붙은 형태여야 한다.
즉,

• w가 n번
• 바로 뒤에 o가 n번
• 바로 뒤에 l이 n번
• 바로 뒤에 f가 n번

이 순서로 나와야 하고, 이런 블록이 여러 번 이어붙을 수 있다.

 

그래서 문자열을 왼쪽부터 차례대로 읽으면서 각 블록의 n을 먼저 구한 뒤,
해당 구간이 정확히 w^n o^n l^n f^n 패턴을 만족하는지 확인하는 방식으로 풀었다.

 

상세 아이디어

1) 한 블록의 w 개수(n) 구하기

int n = 0;
for (int i = index; i < str.size(); i++) // 단어별 n의 개수 찾기
{
	if (str[i] == 'o')
	{
		n = (i - index);
		break;
	}
	else if (str[i] == 'l' || str[i] == 'f')
	{
		cout << 0;
		return 0;
	}
}

• index에서 시작해서 문자열을 보면서,
  • 처음으로 o를 만날 때까지의 w 개수를 n으로 잡는다.
  • o가 나오기도 전에 l이나 f가 나오면, 애초에 w^n o^n ... 형태가 될 수 없으므로 바로 탈락(0 출력)

2) 예외 케이스 체크

if (n == 0 || (index + n * 4 > str.size())) 
{
	cout << 0;
	return 0;
}

 

• n == 0 이면 w가 하나도 없다는 뜻 → 애초에 올바른 블록이 아님.
• 하나의 블록은 w^n o^n l^n f^n 이므로, 길이가 항상 4n 이다.
  현재 위치에서 4n만큼 나갔을 때 문자열을 벗어나면 올바른 블록이 될 수 없다.

3) w^n o^n l^n f^n 패턴 검사

char wolf[4] = { 'w','o','l','f' };

for (int i = index; i < index + (n * 4); i++)
{
    if (str[i] != wolf[(i - index) / n])
    {
        cout << 0;
        return 0;
    }
    i += (n - 1);
}

 

여기서 핵심은 (i - index) / n 이다.

• i가 index에서 index + 4n - 1 까지 증가할 때,
  • index ~ index + n - 1 구간 → (i - index) / n == 0 → wolf[0] == 'w'
  • index + n ~ index + 2n - 1 → 1 → o
  • index + 2n ~ index + 3n - 1 → 2 → l
  • index + 3n ~ index + 4n - 1 → 3 → f

이렇게 구간별로 자동으로 w, o, l, f를 매칭해준다.

그리고 한 번 검사한 뒤, 그 블록의 나머지 문자들은 같은 글자라고 가정하고 i += (n - 1); 로 다음 구간의 첫 글자로 건너뛰는 최적화를 했다. (검사 자체는 n*4 길이 전체를 커버)

 

4) 다음 블록으로 이동

index += (n * 4);

 

• 현재 w^n o^n l^n f^n 블록 하나를 통째로 검증했으므로,
  index를 4n만큼 뒤로 넘겨 다음 블록 검사로 넘어간다.
• 이 과정을 문자열 끝까지 반복하며,
  한 번이라도 규칙이 깨지면 0, 끝까지 통과하면 1을 출력한다.

 

구현 시 주의할 점

• n이 0이 되는 케이스(= w 없이 바로 o, l, f가 나오는 경우)를 꼭 걸러줘야 한다.
• 하나의 블록은 항상 길이가 4n이므로,
  index + n * 4 > str.size()인지 경계 체크를 먼저 해줘야 한다.
• 각 블록을 검사할 때마다 index를 4n만큼 정확히 이동시키지 않으면
  다음 블록 시작 위치가 꼬여서 오답이 나온다.

 

 

---

 

코드

#include <iostream>
#include <string>
using namespace std;

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

	string str = "";
	cin >> str;

	char wolf[4] = { 'w','o','l','f' };
	int index = 0;
	while (index < str.size())
	{
		int n = 0;
		for (int i = index; i < str.size(); i++) // 단어별 n의 개수 찾기
		{
			if (str[i] == 'o')
			{
				n = (i - index);
				break;
			}
			else if (str[i] == 'l' || str[i] == 'f')
			{
				cout << 0;
				return 0;
			}
		}
		if (n == 0 || (index + n * 4 > str.size())) 
		{
			cout << 0;
			return 0;
		}
		for (int i = index; i < index + (n * 4); i++)  // 단어가 순서대로 되어 있는지
		{
			if (str[i] != wolf[(i - index) / n])
			{
				cout << 0;
				return 0;
			}
			i += (n - 1);
		}
		index += (n * 4);
	}
	cout << 1;
	
	return 0;
}