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

1. 문제이해

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

13022번: 늑대와 올바른 단어

 

단어를 입력받아, 해당 단어가 올바른 단어이면 1, 아니면 0 을 출력하는 것이 목표이다.

해당 단어가 늑대나라에서 사용하는 올바른 단어인지 확인하는 규칙은 다음과 같다.

 

1. 임의의 양의 정수 n에 대해서,

'w'가 n번 나오고, 그 다음에 'o'가 n번, 그 다음에 'l'이 n번, 그 다음에 'f'가 n번 나온 단어는 올바른 단어이다.

2. 올바른 단어 2개를 이은 단어도 올바른 단어이다.

3. 1, 2번 조건으로 만들 수 있는 단어만 올바른 단어이다.

 

 

 

2. 문제풀이

 

나를 너무 힘들게한 문제....

풀이하신 분들도 많지 않아서 머리를 쥐어짜가면서 풀이했다.

여러 언어들 풀이방법을 다 찾아봤는데 이해가 잘 안가기도 했고,

안풀린다는 것에 오기가 생겨서 왜 이것도 못하지 라는 마음과 함께 몇 시간을 끙끙댔다.

결국에는 나의 승리로 끝났다.. (야호)

보다 자세하게 풀이를 쓰려고 노력했으니 많은 분들께 도움이 되었으면 한다.

 

 

생각보다 문제의 조건이 까다롭다.

언뜻 보면 간단하지만, 반례가 상당히 많은 문제이다.

결론부터 말하자면, 필자는 아래와 같은 방식으로 해당 문제를 풀이했다.

 

---

1. w, o, l, f 의 갯수를 세고, 갯수가 같지 않다면 올바르지 않은 단어 ➡ 0 반환

 

 

2. w, o, l, f 의 갯수가 모두 같다면, 올바른 단어인지 확인

 

2 - 1. 1번 규칙을 만족하는지 확인

➡ 예를 들어, w의 갯수(모두 갯수가 같으므로 대표적으로 w의 갯수만 확인) 가 3이면,

wwwooolllfff 인지 확인. 맞다면 올바른 단어 ➡ 1반환. 아니라면 2 - 2 로.

 

2 - 2. 2번 규칙을 만족하는지 확인

➡ 예를 들어, w의 갯수(모두 갯수가 같으므로 대표적으로 w의 갯수만 확인) 가 3이면,

w의 개수를 하나씩 줄여나가며, 1번 규칙을 만족하는 단어를 만들고, 해당 단어가 포함되어있는지 확인.

단어가 포함되어있다면 해당 부분을 '*' 로 치환.

모든 단어가 '*' 로 치환되면 올바른 단어이므로 ➡1 반환, 아니라면 ➡ 0 반환

---

 

2 - 2번이 가장 중요한 부분인데, 이해가 되지 않는 분들이 몇몇 계실거라 생각된다.

아래 2개의 예제를 보자.

(아래 예제 모두 w, o, l, f 의 개수가 같다. 모든 갯수가 같으므로 대표적으로 w의 갯수만 확인했다.)

 

ex 1) wwoollffwolf (올바른 단어 여러개가 이어진 경우) , w = 3

2 -1 에서, wwwooolllfff 가 아닌것을 확인했으므로 2 - 2로 이동.

w 값에 -1 해나가며 1번 규칙을 만족하는 단어를 만들고, 포함되었는지 확인

포함되어있다면, 해당 부분을 '*'로 치환
w = 2 인 경우) wwoollff 만들고 해당 단어가 포함되었는지 확인.

포함되었으면 해당 부분을 '*'로 대체. ➡ ********wolf

w = 1 인 경우) wolf 만들고 해당 단어가 포함되었는지 확인

포함되었으면 해당 부분을 '*'로 대체. ➡ ************

단어에 '*' 가 아닌 부분이 없으므로 '올바른 단어'
      
   ex 2) wwoowolfllff (올바른 단어 사이에 올바른 단어가 삽입된 경우) , w = 3
  2 -1 에서, wwwooolllfff 가 아닌것을 확인했으므로 2 - 2로 이동.
  w 값에 -1 해나가며 1번 규칙을 만족하는 단어를 만들고, 포함되었는지 확인

포함되어있다면, 해당 부분을 '*'로 치환

w = 2 인 경우) wwoollff 만들고 해당 단어가 포함되었는지 확인.

포함되지 않았으므로 해당 부분 건너뜀.

w = 1 인 경우) wolf 만들고 해당 단어가 포함되었는지 확인
포함되었으면 해당 부분을 '*'로 대체. ➡ wwoo****llff

단어에 '*' 가 아닌 부분이 있으므로 '올바르지 않은 단어'

 

 

위와 같은 방식을 통해 2 - 2 에서 최종적으로 올바른 단어와 그렇지 않은 단어를 분류해주었다.

이제 아래 코드를 살펴보자.

 

 

 

3. 소스코드

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

// 1번 규칙으로 단어 만드는 함수
string make_word(int w) {
	string make_word;

	for (int i = 0; i < w; i++) {
		make_word += 'w';
	}

	for (int i = 0; i < w; i++) {
		make_word += 'o';
	}

	for (int i = 0; i < w; i++) {
		make_word += 'l';
	}

	for (int i = 0; i < w; i++) {
		make_word += 'f';
	}

	return make_word;
}

// 올바른 단어인지 체크하는 함수
int check_wolf_word(string word) {
	string right_word;
	int w = 0;
	int o = 0;
	int l = 0;
	int f = 0;

	// 단어에 포함된 w, o, l, f 의 개수를 세어줌
	for (int i = 0; i < word.size(); i++) {
		if (word[i] == 'w') {
			w++;
		}
		else if (word[i] == 'o') {
			o++;
		}
		else if (word[i] == 'l') {
			l++;
		}
		else if (word[i] == 'f') {
			f++;
		}
	}

	// 1. 알파벳의 개수가 같지 않다면 올바르지 않은 단어
	if (w != o || w != l || w != f || o != l || o != f || l != f) {
		cout << "0";
		return 0;
	}

	// 2. 알파벳의 개수가 같다면 올바른 단어인지 확인
	else {
		// 2 - 1. 1번 규칙을 만족하는지 확인
		if (word == make_word(w)) {
			cout << "1";
			return 0;
		}

		// 2 - 2. 2번 규칙을 만족하는지 확인
		else {
			/* 
			   각 단어의 개수 - 1 해주며 만족하는 단어를 만들어 나감.
			   단어가 입력받은 단어에 포함되어있다면, 그 부분을 '*' 로 대체
			   만약 '*' 로 모두 대체된다면 올바른 단어. 아니면 옳지 않은 단어
			   */
			for (int i = 1; i < w; i++) {
				right_word = make_word(w - i);
				while (word.find(right_word) != -1) {
					int size = right_word.size();
					string star;
					for (int i = 0; i < size; i++) {
						star += '*';
					}
					word.replace(word.find(right_word), 
                    						size, star);
				}
			}
			
			for (int i = 0; i < word.size(); i++) {
				if (word[i] != '*') {
					cout << "0";
					return 0;
				}
			}

			cout << "1";
			return 0;
			
		}
	}

	return 0;
}


int main() {
	string word;

	cin >> word;
	check_wolf_word(word);

	return 0;
}

2. 문제풀이에서 도출한 풀이방식과 동일한 방법을 이용한 코드이다.

메인함수에서는 단어만 입력받고, 해당 단어가 올바른 단어인지는 check_wolf_word 함수에서 판별했다.

 

make_word 함수는 정수 w를 인자로 받아, 해당 값만큼 1번 규칙에 해당하는 단어를 생성하는 함수이다.

예를 들어 인자로 1이 들어오면 wolf, 2가 들어오면 wwoollff를 반환한다.

check_wolf_word 함수는 입력받은 단어가 올바른 단어인지 판별하는 함수이다.

앞서 이야기한대로, 다음과 같은 규칙에 따라 단어를 판별한다.

 

1. w, o, l, f 의 갯수를 세고, 갯수가 같지 않다면 올바르지 않은 단어 ➡ 0 반환

 

2. 2. w, o, l, f 의 갯수가 모두 같다면,

2 - 1. 2 - 1 . 1번 규칙을 만족하는지 확인

➡ 맞다면 올바른 단어 ➡ 1반환. 아니라면 2 - 2 로.

2 - 2. 2 - 2. 2번 규칙을 만족하는지 확인

w의 개수를 하나씩 줄여나가며, 1번 규칙을 만족하는 단어를 만들고, 해당 단어가 포함되어있는지 확인.

단어가 포함되어있다면 해당 부분을 '*' 로 치환.

모든 단어가 '*' 로 치환되면 올바른 단어이므로 ➡1 반환, 아니라면 ➡ 0 반환

 

주석없는 코드는 왼쪽 아래 더보기를 참고 바랍니다.😊

<주석 없는 코드>

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

string make_word(int w) {
	string make_word;

	for (int i = 0; i < w; i++) {
		make_word += 'w';
	}

	for (int i = 0; i < w; i++) {
		make_word += 'o';
	}

	for (int i = 0; i < w; i++) {
		make_word += 'l';
	}

	for (int i = 0; i < w; i++) {
		make_word += 'f';
	}

	return make_word;
}

int check_wolf_word(string word) {
	string right_word;
	int w = 0;
	int o = 0;
	int l = 0;
	int f = 0;

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

	if (w != o || w != l || w != f || o != l || o != f || l != f) {
		cout << "0";
		return 0;
	}

	else {
		if (word == make_word(w)) {
			cout << "1";
			return 0;
		}

		else {
			for (int i = 1; i < w; i++) {
				right_word = make_word(w - i);
				while (word.find(right_word) != -1) {
					int size = right_word.size();
					string star;
					for (int i = 0; i < size; i++) {
						star += '*';
					}
					word.replace(word.find(right_word), 
                    						size, star);
				}
			}
			
			for (int i = 0; i < word.size(); i++) {
				if (word[i] != '*') {
					cout << "0";
					return 0;
				}
			}

			cout << "1";
			return 0;
			
		}
	}

	return 0;
}


int main() {
	string word;

	cin >> word;
	check_wolf_word(word);

	return 0;
}

 

 

---

문제를 풀고 나서 엄청나게 짜릿했다..

됐다!! 를 외치면서 10분동안 온집안을 방방 뛰어다녔다.

처음에는 '*' 로 치환하지 않고, 삭제해주었는데, 그렇게 되면 wowolflf 같은 경우,

wowolflf ➡ wolf ➡ 모두 없어지므로 올바른 단어?

가 되어버리기 때문에 안되더라..😥

그리고 한가지 더.. 파이썬은 코드가 무척이나 간단하더라..^^

진짜 파이썬으로 바꿔야 할까 진지하게 고민해봐야겠다..

 

문제에 대한 질문이나 지적은 언제나 감사하게 받고있습니다.😊