5550. 나는 개구리로소이다(D4)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWxqfhKAWgDFAW4&categoryId=AWWxqfhKAWgDFAW4&categoryType=CODE

이 문제의 핵심은 간단하다. 우선, 개구리가 몇 번을 울 수 있다는 제한이 없다. 개구리는 몇 번이고 울 수 있다. 하지만 'c' 'r' 'o' 'a' 'k' 의 문자를 순서대로 말해야 한다. 즉, 한 개구리가 5글자를 말하기 전에 울음소리가 시작된다면 이는 최소 2마리가 필요하다는 뜻이 된다.

문제 정의 및 해결방법을 떠나서 가장 먼저 고민했던 부분은 입력이 들어오는 형태이다.

입력을 잘 살펴보면, 한 테스트케이스에 몇 개의 문자가 들어올 지 알 수 없다. 이 때, 방법은 2가지로 나뉜다.

i) 문자열의 길이가 2500이하로 정해져 있기 때문에 char[2500] 짜리 배열을 만들어서 줄 단위로 받는다.

ii) 배열이 아닌 char를 만들어서 문자 하나가 들어올 때마다 진행하며 라인의 끝 즉, 개행문자가 들어오는 경우를 확인한다.

알고리즘 문제를 매번 풀고 있지만 문자열의 입력이 들어올 때는 우선 긴장부터 된다. 카카오 블라인드 채용 때도 그랬고 다른 경우에도 그렇다. 이는 문자열이 숫자에 비해 다루기 까다로운 점도 있지만 익숙하지 않으며 충분한 연습이 되어있지 않다는 것을 뜻이다. 확실하게 공부해야 할 필요성을 느꼈다.

이 문제에서는 i)번 경우를 사용했다. 차이를 조금 둬서 char[2500] 대신 String에 입력을 받고 at()을 사용해서 문자를 확인했다.

이제 본격적인 해결방법을 알아보자.

핵심은 이렇다. 

- 'c'가 등장한다면 한 가지가 시작된 것

- 'k'가 등장한다면 한 울음소리가 끝났고 끝난 울음소리가 다시 등장할 수 있다는 것

- 'c', 'r', 'o', 'a', 'k'가 순서대로 등장하지 않은 것

- 앞의 문자가 나오지 않은 상태에서 뒤의 문자가 나온 것 [ ex) rcoakcroak ]

개구리의 울음소리를 잠깐 벗어나보자. 

위 그림을 보면 a, b, c, d 4마리 개구리가 있다. 개구리는 느리게 울 수도 있으며 빠르게 울 수도 있다. b와 c처럼 2번 씩 울 수도 있다. 이런 상황에서 그림의 빨간 선처럼 모든 구간을 살폈을 때의 상황을 만족하기 위해 필요한 최소의 개구리 수를 구하는 문제이다.

이를 위해서 매 상황마다 현재 울음소리가 진행되고 있는 개구리의 수를 알아야 하고 이 값이 최대가 되는 지점이 최소로 필요한 개구리의 수이다. 

해결방법은 비교적 간단하다.

'c' 'r' 'o' 'a' 'k' 각 상태에 머무르고 있는 개구리의 수를 알기 위한 int[5] 배열, 나올 수 없는 경우가 나왔음을 파악하기 위한 bool, 매 문자가 들어온 구간마다 필요한 개구리의 수를 파악하기 위한 int가 필요하다.

'c'가 들어올 경우 croak[0]의 값을 늘린다. 이는 1마리의 개구리가 울음소리를 시작했고 'c'만 말했음을 의미한다. 다음으로 'r'이 들어올 경우 croak[0]의 값을 1 빼고 croak[1]의 값을 1 늘린다. 이는 1마리의 개구리가 울음소리 중이며 'r'까지 말했음을 의미한다. 마찬가지 방법으로 들어오는 문자마자 순서상 전 문자를 1 깎고 들어온 문자의 값을 1 늘린다. 이 때, 들어오면 안되는 문자가 들어온 것을 확인할 필요가 있다. 만약 순서상의 오류가 있는 상태로 문자가 들어왔다면 전 문자를 1 깎는 과정에서 값에 오류가 생길 것이다. 매 과정을 진행하면서 전 문자에 저장되어 있는 값이 0보다 작아졌는지를 확인해야 한다. 이 문제는 최종적으로 몇 번을 울었는지에 대한 정보는 필요하지 않기 때문에 'k'가 들어왔을 경우는 전 문자의 값은 깎되 k 문자의 값은 무시한다.

다음으로, 'c' 'r' 'o' 'a' 까지 정상적으로 울었지만 마무리가 되지 않은 경우가 생길 수 있다. 그러므로 마지막에 'c' 'r' 'o' 'a'의 나온 횟수를 기록한 배열에 0이 아닌 값이 존재하는지 확인한다. 울음소리가 끝나지 않은 개구리가 존재한다는 뜻이므로 -1을 출력해야 한다.

마지막으로 매 루틴마다 'c' 'r' 'o' 'a' (진행중인 울음소리의 횟수)를 모두 더한 값과 지금까지의 최대값을 비교하여 더 큰 값을 최대값으로 한다. 이 값은 오류가 존재하지 않을 경우 최종적으로 필요한 최소 개구리 수가 된다.

- 소스 코드 -

#include<iostream>
#include<algorithm>
#include<string>
 
using namespace std;
 
int main(void) {
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        int croak[5] = { 0 };
        char c;
        string str;
        cin >> str;
        int count = 0;
        bool flag = true;
        for (int i = 0; i < str.length(); i++) {
            c = str.at(i);
            switch (c) {
            case 'c':
                croak[0]++;
                break;
            case 'r':
                croak[1]++;
                croak[0]--;
                if (croak[0] == -1) {
                    flag = false;
                }
                break;
            case 'o':
                croak[2]++;
                croak[1]--;
                if (croak[1] == -1) {
                    flag = false;
                }
                break;
            case 'a':
                croak[3]++;
                croak[2]--;
                if (croak[2] == -1) {
                    flag = false;
                }
                break;
            case 'k':
                croak[3]--;
                if (croak[3] == -1) {
                    flag = false;
                }
                break;
            }
            count = max(count, croak[0] + croak[1] + croak[2] + croak[3]);
        }
        if (croak[0] != 0 || croak[1] != 0 || croak[2] != 0 || croak[3] != 0) {
            flag = false;
        }
        if (!flag) {
            count = -1;
        }
        
        printf("#%d %d\n", test_case, count);
    }
}