[백준] 12933번 : 오리 (C++)

12933번 : 오리

---

문제)

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

 

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

 

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

 

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

 

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

 

 

 

입력 :

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

 

 

 

 

출력 :

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

 

 

 

 

 

풀이)

오리가 더 이상 나오지 않을 때까지 (체크하지 않은 q가 나오지 않을 때) 한마리씩 울음소리를 제거하여 풀었다.

 

// 12933. 오리
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
string s;
vector<bool> vec;
 
int duck = 0;
int main()
{
    cin >> s;
    vec.resize(s.length(), 0);
 
 
    
    bool flag = 1;
 
    bool x = 0;
    while (flag)
    {
        flag = 0;
        int cnt = 0;
        bool done = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == 'q' && !vec[i] && cnt == 0)
            {
                cnt++;
                vec[i] = 1;
                flag = 1;
            }
            else if (s[i] == 'u' && !vec[i] && cnt == 1)
            {
                cnt++;
                vec[i] = 1;
            }
            else if (s[i] == 'a' && !vec[i] && cnt == 2)
            {
                cnt++;
                vec[i] = 1;
            }
            else if (s[i] == 'c' && !vec[i] && cnt == 3)
            {
                cnt++;
                vec[i] = 1;
            }
            else if (s[i] == 'k' && !vec[i] && cnt == 4)
            {
                cnt = 0;
                vec[i] = 1;
                done = 1;
            }
        }
        if (done) duck++;
 
        // 불완전하게 끝났을 경우
        if (cnt)
        {
            x = 1;
            break;
        }
    }
 
    // 순서가 잘못되거나, 잘못된 알파벳이 나와 체크가 되지 못한
    // 문자가 있다면
    for (int i = 0; i < s.length(); i++)
    {
        if (!vec[i])
        {
            x = 1;
        }
    }
 
    if (x || !duck)
    {
        cout << -1;
    }
    else
    {
        cout << duck;
    }
 
    return 0;
}
 

---

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

12933번: 오리