[백준] 12933번 - 오리 / C++

문제

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

영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.

갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.

녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q', 'u', 'a', 'c', 'k'로만 이루어져 있다.

 

출력

영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string str;
string target = "quack";
int res;

bool get_count()
{
	vector<int> duck;
	int s, e, i;
	int idx = 0;

	// 녹음한 소리 전체를 확인
	while (idx < str.size())
	{
		// 소리가 어디부터 시작하는지 찾기
		s = find(target.begin(), target.end(), str[idx]) - target.begin();
		e = s;
		// 이어지는 소리의 최대 길이 구하기
		while (idx < str.size() && e < target.size() && str[idx] == target[e])
		{
			idx++;
			e++;
		}
		// 소리의 처음부터 시작하는 경우
		if (s == 0)
		{
			// 새로운 오리이므로 duck에 추가 후 존재하는 오리의 수 갱신
			duck.push_back(e);
			res = max(res, (int)duck.size());
			// 소리가 끝났다면 duck에서 삭제
			if (e - s == target.size())
				duck.pop_back();
			continue;
		}
		// 소리의 중간부터 시작하는 경우 
		// 앞 부분의 소리가 duck에 존재하는지 확인
		i = find(duck.begin(), duck.end(), s) - duck.begin();
		// 존재하지 않으면 올바르지 않음 -> false를 리턴
		if (i == duck.size())
		{
			return false;
		}
		// 존재하면 누적된 소리의 길이를 갱신
		duck[i] = e;
		// 소리가 끝났다면 duck에서 삭제
		if (e == target.size())
		{
			duck.erase(duck.begin() + i);
		}	
	}
	// 끝나지 않고 남은 소리가 있다면 올바르지 않음 -> false 리턴
	if (!duck.empty())
		return false;
	return true;
}

int main() 
{
	cin >> str;
	// 녹음한 소리가 올바른 경우
	if (get_count())
		cout << res << endl;
	// 녹음한 소리가 올바르지 않은 경우
	else
		cout << -1 << endl;
	return 0;
}

 

오리 한 마리는 연속해서 여러 번 울 수는 있지만 동시에 여러 번 울 수는 없다. 녹음한 소리를 확인하여 현재 진행 중인 소리의 누적된 길이를 duck에 저장한다. 이때 duck의 길이가 늘어나기 때문에 오리의 수를 갱신한다. duck의 크기는 동시에 우는 오리의 수라고 할 수 있고, 이 값이 오리의 최소 개수가 된다. 울음소리가 끝나면 duck에서 삭제하여 같은 오리의 다음 울음소리를 확인할 준비를 한다. 만약 중간에 이어지지 않는 소리가 확인되거나 녹음을 끝까지 확인했음에도 끝나지 않은 소리가 있다면 그 녹음은 올바르지 않다고 할 수 있다. 이 경우 false를 리턴하여 -1을 출력하도록 한다.

녹  음 : quqacukqauackck
오리 1 : qu_ac_kq_uack__
오리 2 : __q__u__a____ck
WHILE : _12_34567___8_9

예를 들어 위의 입력에 대해 duck의 상태는 다음과 같이 변한다.

 

링크

12933번: 오리

inbdni/Baekjoon