[BOJ] 12933번_오리_그리디 (C++)

[문제]

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

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.

방에 오리가 여러마리 존재할 때, 울음 소리를 듣고 오리가 몇 마리인지 세려고 한다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야한다. "quqacukqauackck"과 같은 경우는 두 마리의 오리가 울었다고 볼 수 있다.

입력으로 오리의 울음소리가 주어졌을 때, 방에 몇마리의 오리가 존재하는지 구하는 문제이다.

[사용 알고리즘]

그리디

[풀이 핵심]

• 입력받은 오리 울음소리 문자열을 처음부터 끝까지 탐색하며 "quack"이 순서대로 나올 때마다 오리가 1마리 존재한다 생각하고 visited[]배열에 체크하여 방금 탐색한 quack을 다음에 탐색하지 않도록 하여 풀었다.
• 핵심은 quack이 연속적으로 나올경우 한 오리가 운다음 연속해서 울었다고 판단해야하므로 bool타입 check변수를 통해 판단해줘야한다.
• 마지막으로 입력받은 오리 울음소리를 전부 탐색했는지 확인하고 전부 탐색안했으면, 잘못된 울음소리이므로 -1을 출력하고, 전부 탐색했으면 result를 출력해주면된다.

[코드]

//boj12933번_오리_그리디 알고리즘

#include<iostream>
#include<vector>

using namespace std;

bool visited[2501];

int main() {
	string str;
	cin >> str;

	int result = 0;

	for (int i = 0; i < str.size(); i++) {
		string temp = "";
		vector<int> v;
		bool check = false;

		for (int j = i; j < str.size(); j++) {
			if (str[j] == 'q' && !visited[j] && temp == "") {
				temp += 'q';
				v.push_back(j);
			}
			else if (str[j] == 'u' && !visited[j] && temp == "q") {
				temp += 'u';
				v.push_back(j);
			}
			else if (str[j] == 'a' && !visited[j] && temp == "qu") {
				temp += 'a';
				v.push_back(j);
			}
			else if (str[j] == 'c' && !visited[j] && temp == "qua") {
				temp += 'c';
				v.push_back(j);
			}
			else if (str[j] == 'k' && !visited[j] && temp == "quac") {
				temp += 'k';
				v.push_back(j);
			}

			if (temp == "quack") {
				temp = "";

				if (!check) {
					check = true;
					result++;
				}

				for (int k = 0; k < v.size(); k++) {
					visited[v[k]] = true;
				}
			}
		}
	}

	bool flag = false;

	for (int i = 0; i < str.size(); i++) {
		if (!visited[i]) {
			flag = true;
			break;
		}
	}

	if (flag) {
		cout << -1;
	}
	else {
		cout << result;
	}

	return 0;
}