문제 개요
개구리 울음소리를 나타내는 문자열 croakOfFrogs가 주어집니다. 이 문자열에는 여러 마리 개구리가 내는 "croak" 소리가 뒤섞여 있으며, 여러 개구리가 동시에 운다는 점이 특징입니다. 우리의 목표는 주어진 문자열의 모든 울음소리를 완성하기 위해 필요한 최소 개구리 수를 구하는 것입니다.
여기서 유효한 "croak"란 한 마리 개구리가 'c', 'r', 'o', 'a', 'k' 다섯 글자를 순서대로 발성하는 것을 의미합니다. 개구리는 반드시 다섯 글자를 모두 내야 하나의 울음소리가 완성되며, 만약 문자열이 유효한 "croak" 조합이 아니라면 -1을 반환해야 합니다.
예를 들어 입력이 "crcoakroak"라면 출력은 2가 됩니다. 첫 번째 개구리가 c-r-o-a-k를 운 도중에 두 번째 개구리가 'c'부터 울기 시작했기 때문에, 두 마리가 동시에 우는 구간이 존재하기 때문입니다.
풀이 전략
이 문제는 각 글자의 등장 횟수를 추적하면서, 동시에 운다는 개구리 수의 최댓값을 계산하는 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 'c'가 등장하면 새 개구리가 울기 시작한 것이므로 현재 운다 중인 개구리 수(temp)를 1 증가시킵니다.
- 'k'가 등장하면 한 마리의 울음이 끝난 것이므로 temp를 1 감소시킵니다.
- temp의 최댓값(ret)을 계속 갱신하면 그 값이 곧 필요한 최소 개구리 수입니다.
- 매 단계마다 글자별 누적 횟수가 'c' ≥ 'r' ≥ 'o' ≥ 'a' ≥ 'k' 순서를 유지하는지 검사해 유효성을 확인합니다.
- 모든 문자를 처리한 뒤 다섯 글자의 총 등장 횟수가 모두 같은지 확인하고, 같지 않으면 -1을 반환합니다.
단계별 알고리즘
- 문자별 등장 횟수를 저장할 맵 m을 정의합니다.
- 크기 5의 배열 ch를 {'c', 'r', 'o', 'a', 'k'}로 초기화합니다.
- temp := 0, ret := 0으로 설정합니다.
- 문자열 s의 각 문자 c에 대해 다음을 수행합니다.
- m[c]를 1 증가시킵니다.
- maxVal := m[ch[0]]으로 설정합니다.
- i를 0부터 4까지 순회하면서, maxVal < m[ch[i]] 또는 m[ch[i]] < 0이면 -1을 반환합니다.
- maxVal := m[ch[i]]로 갱신합니다.
- c가 'c'이면 temp를 1 증가시키고, 'k'이면 temp를 1 감소시킵니다.
- ret := max(ret, temp)로 갱신합니다.
- 모든 문자를 처리한 후, i를 1부터 4까지 순회하면서 m[ch[0]] != m[ch[i]]이면 -1을 반환합니다.
- ret을 반환합니다.
C++ 구현 코드
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minNumberOfFrogs(string s) {
map<char, int> m;
char ch[5] = { 'c', 'r', 'o', 'a', 'k' };
int temp = 0;
int ret = 0;
for (auto& c : s) {
m[c]++;
int maxVal = m[ch[0]];
for (int i = 0; i < 5; i++) {
if (maxVal < m[ch[i]] || m[ch[i]] < 0) {
return -1;
}
maxVal = m[ch[i]];
}
if (c == 'c') {
temp++;
}
else if (c == 'k') {
temp--;
}
ret = max(ret, temp);
}
for (int i = 1; i < 5; i++) {
if (m[ch[0]] != m[ch[i]])
return -1;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.minNumberOfFrogs("crcoakroak"));
}
입력
"crcoakroak"
출력
2
복잡도 분석
시간 복잡도는 문자열의 길이를 n이라 할 때 각 문자마다 최대 5번의 비교를 수행하므로 O(n)입니다. 공간 복잡도는 다섯 글자에 대한 카운트만 저장하면 되므로 O(1)입니다.