백준 12933 오리 C++

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

12933번: 오리

---

문제

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

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

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

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

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

---

입력

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

---

출력

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

---

고려해야 할 것이 많은 문제였고, 올바른 오리의 울음소리가 뭔지 판별하는 것도 어려웠다..

별다른 알고리즘이 필요하지 않았고, 완전탐색 + 문자열을 사용해야 했다.

먼저 예제가 많이 주어지는데 예제를 보면서 올바른 문자열/ 올바르지 않은 문자열의 조건을 하나하나 생각해본다.

 

예제1) 

quqacukqauackck

quqacukqauackck

이 문자열은 올바른 문자열이다. 왜 올바른 문자열인지 알아보자.

먼저 오리의 울음 순서는 q->u->a->c->k를 만족해야 한다.

오리가 한마리 있다고 생각해보자.

오리는 quack순서로 우니깐 첫번쨰 오리는 quackquack 이렇게 울 것이다.

 

원본의 문자열 에서 quackquack순서대로 찾아서 이것을 제거해보자.

quqacukqauackck 에서 quackquack는 quqacukqauackck 빨간색 부분에 존재한다.

즉 , 오리 한마리가 존재한다.

이제 빨간색으로 칠한 부분을 제외하고 생각해보자. 빨간 부분을 원본 문자열에서 제거하면

quack가 남는다.

이제 오리가 한마리 더있다고 하자. (두 마리)

두번쨰 오리가 울면 

quack 파란색 부분을 두번쨰 오리가 운다.

이제 남은 문자열은 존재하지 않는다. 즉 예제 1에서 오리는 최소 2마리 존재한다.

---

예제2)

kcauq

이 문자열은 올바르지 않다. q->u->a->c->k의 순서를 어겼기 때문이다.

---

예제3)

quackquackquackquackquackquackquackquackquackquack

quackquackquackquackquackquackquackquackquackquack

이 문자열에서 첫번쨰 오리가 존재한다고 생각해보자.

오리는 quack -> quack- > quack ->...이렇게 운다.

즉, 첫번쨰 오리가 

quackquackquackquackquackquackquackquackquackquack

모두 이 울음소리를 내고, 오리는 최소 한 마리 존재한다.

---

예제 4)

qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk

qqqqqqqqqquuuuuuuuuuaaaaaaaaacccccccccckkkkkkkkkk

이 예제는 오리가 최소 10마리 있어야 한다.

일단 첫번쨰 오리가 운다고 생각하자.

첫번쨰 오리는 빨간색으로 표현한다.

qqqqqqqqqquuuuuuuuuuaaaaaaaaacccccccccckkkkkkkkkk

 

두번쨰 오리는 파란색으로 표현한다.

qqqqqqqqquuuuuuuuuuaaaaaaaaacccccccccckkkkkkkkkk

이와 같은 과정을 통해 최소 오리는 10마리 있음을 생각 할 수 있다.

---

예제 5)

quackqauckquack

quackqauckquack

개인적으로 이 예제에서 많이 고생했다. 처음 오리는 quackquack이렇게 울면

quackqauckquack

빨간색으로 쳐진 부분이 첫번쨰 오리이다.

이제 두번째 오리가 울려고 하는데, 순서를 만족하지 않는다 (ackqu) . 즉 올바른 울음소리가 아니다.

 -> 이 부분에서 예외 처리를 하였다.

---

#include <iostream>
#include <string>
using namespace std;

bool check_index[2501]; //울음소리를 만족하면 인덱스 true로 바꿈

int main(void){
    int ans = 0; //오리 숫자
    
    string str;
    cin >> str;
    for(int i = 0;i<str.size();i++){
        string temp = "";
        bool valid = false; 
        int index[5] = {0, }; //quack의 인덱스 저장
        
            /*올바른 오리 울음소리 찾기 */
            for(int j = i;j<str.size();j++){
                if(check_index[j] == false){
                    if(str[j] == 'q' && temp == ""){ //q이고 temp가 빈 문자열인 경우
                        index[0] = j;     //index[0]에 q 인덱스 저장
                        temp = temp + 'q'; //temp -> q로 바꿈
                    }
                    if(str[j] == 'u' && temp == "q"){ //u이고 temp가 q인 경우
                        index[1] = j;    //index[1]에 u인덱스 저장
                        temp = temp + 'u'; //temp -> qu로 바뀜
                    }
                    else if(str[j] == 'a' && temp == "qu"){ //a이고 temp가 qu인경우
                        index[2] = j;         //index[2]에 a인덱스 저장
                        temp = temp + 'a';    //temp ->qua로 바뀜
                    }
                    else if(str[j] == 'c' && temp == "qua"){ //c이고 temp가 qua인 경우
                        index[3] = j;        //index[3]에 c인덱스 저장
                        temp = temp + 'c';    //temp->quac로 바뀜
                    }
                    else if(str[j] == 'k' && temp == "quac"){ //k이고 temp가 quac인 경우
                        index[4] = j;        //index[4]에 k인덱스 저장
                        temp = temp + 'k';    //temp->quack로 바뀜
                    }
                }
            
                /*quack일때 temp를 빈 문자열로 바꾸고 인덱스가 오름차순인지 확인*/
                if(temp == "quack"){
                    temp = "";
                    if(index[0] < index[1] && index[1] < index[2] && index[2] < index[3] &&
                      index[3] < index[4]){
                        /*valid가 false인 경우 true로 바꾸고 ans++
                        -> 오리가 연속해서 우는 경우 ans를 갱신 할 필요 없음 */
                        if(valid == false){
                            valid = true;
                            ans++;
                        }
                        /*quack 인덱스 true 처리*/
                        check_index[index[0]] = 1;
                        check_index[index[1]] = 1;
                        check_index[index[2]] = 1;
                        check_index[index[3]] = 1;
                        check_index[index[4]] = 1;
                        
                    }
                    
                }
            }
        }
    
    /*인덱스가 false인 것이 있으면 올바르지 않은 울음소리 */
    for(int i = 0;i<str.size();i++){
        if(check_index[i] == 0){
            cout << -1;
            return 0;
        }
    }

    
    cout << ans;
}