[BOJ] 12933 오리 c++

문제 링크

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

핵심 알고리즘

나는 하나의 오리가 낼 수 있는 연속적인 "quack"를 stack에 담아서 처리하는 방식을 생각했다

순서에 맞게 k가 들어오면 flag = 1로 하여 오리 울음소리가 있음을 판단하고

stack에 들어가지 못하는 값은 다음 오리 판단시에 쓰이기 위해 tmp에 저장했다

flag = 1이거나 울음소리가 잘 끝나 스택 사이즈가 0이라면 while문을 다시 돌아 다음 오리 울음소리를 판단한다

울음소리가 하나라도 없거나 울다가 만 "quackqua"과 같은 값이라면 -1을 처리한다

나는 계속 77퍼에서 틀렸습니다가 나왔는데 5의 배수가 아닌 값을 while문 뒤에다가 옮겼더니 맞았다

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <unordered_map>
#include <map>
#include <cmath>
#include <sstream>
#include <list>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string str;
    cin >> str;

    int ans = 0;

    while (str.size() >= 5) {

        string tmp;
        stack<char> s;
        int flag = 0;

        for (int i = 0; i < str.size(); i++) {

            if (s.size() == 0 && str[i] == 'q')
                s.push(str[i]);
            else if (str[i] == 'u' && !s.empty() && s.top() == 'q')
                s.push(str[i]);
            else if (str[i] == 'a' && !s.empty() && s.top() == 'u')
                s.push(str[i]);
            else if (str[i] == 'c' && !s.empty() && s.top() == 'a')
                s.push(str[i]);
            else if (str[i] == 'k' && !s.empty() && s.top() == 'c') {
                flag = 1;
                while (!s.empty())
                    s.pop();
            }
            else
                tmp += str[i];
        }

        if (flag == 1 && s.size() == 0) {
            str = tmp;
            ans++;
        }
        else {
            ans = -1;
            str = tmp;
            break;
        }
    }

    if (str.size() % 5 != 0)
        ans = -1;

    cout << ans;
}