[백준/c++] 오리

문제

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

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

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

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

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

입력

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

출력

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

구현해야 할 조건

처음 오리를 측정할때, q가 나오면 새로운 오리가 나온다는 생각으로 접근했다가.. 첫 예제부터 안풀려서 다시 생각을 했다. 즉, q가 나온다고해서 오리가 되는 것은 아니니까,,,

q라는게 낱말이 나오면 duck벡터에서 'q'를 넣기전에 'k'이거나 아무것도 없어야 된다는 조건이 만들어 진다. 나머지 uack에 대해서도 vector.back()을 전체 확인하면서 내려가면 된다. 2500길이면 quack의 길이로 나누면 50마리가 되니까 아주 아주 아주 간단한 계산을 통해서 12,500,000번 반복이 최대이다. 사실 최대가 아닐 수도 있다.

code 

#include<iostream>
#include<vector>
#include<string>
#include<map>

using namespace std;

string str = "";
vector<vector<int> > duck;

map<char,int> m = {{'q',1},{'u',2},{'a',3},{'c',4},{'k',5}}; // 간편하게 해결하기 위해서 숫자로 치환 map을 사용해서
bool chk = true;

int main()
{
	
	bool chk = true;
	cin >> str;
	
	for(int i = 0; i < str.length(); i++)
	{
		int c = m[str[i]];
		
		bool insert = false;
		
		for(int j = 0; j < duck.size(); j++)
		{
			if(duck[j].back() == (c == 1 ? 5 : c - 1)) // duck vector의 back이 단어가 q이면 5이거나 다른 단어이면 c-1 이여야 한다.
			{
				duck[j].push_back(c);
				insert = true;
				break;
			}
		}
		
		if(!insert) // 첫 오리를 넣어주는 장소 or 새로운 오리를 만들어주는 장소
		{
			if(c == 1)
				duck.push_back({1});
			else
			{
				chk = false;
			}
		}
	}
	
	for(int i = 0; i < duck.size(); i++) // 오리 검사 
	{
		if(duck[i].back() != 5)
		{
			chk = false;
			break;
		}
	}
	
	if(chk)
	{
		cout << duck.size();
	}
	else
	{
		cout << -1;
	}
	
	return 0;
}