croakOfFrogs라는 문자열이 있다고 가정합니다. 이것은 다른 개구리의 "croak" 문자열의 조합을 나타냅니다. 여러 개구리가 동시에 삐걱거릴 수 있으므로 여러 "croak"이 혼합됩니다. 주어진 문자열의 모든 꽥꽥거리는 소리를 끝내기 위해 서로 다른 개구리의 최소 수를 찾아야 합니다.
여기서 유효한 "croak"은 개구리가 5개의 문자 'c', 'r', 'o', 'a', 'k'를 순차적으로 생성한다는 의미입니다. 개구리는 크로크를 끝내기 위해 다섯 글자를 모두 생성해야 합니다. 문자열이 유효한 "croak" 문자열이 아니면 -1을 반환합니다.
따라서 입력이 "crcoakroak"과 같으면 첫 번째 개구리가 "crcoakroak"을 외칠 수 있으므로 출력은 2가 됩니다. 두 번째 개구리는 나중에 "crcoakroak"라고 외칠 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 맵 정의
-
ch 크기의 배열을 정의합니다. 5 {'c', 'r', 'o', 'a', 'k'}로 할당합니다.
-
temp :=0, ret :=0
-
s의 각 요소 c에 대해
-
(m[c]를 1씩 증가)
-
maxVal :=m[ch[0]]
-
initialize i :=0의 경우, i <5일 때 업데이트(i 1만큼 증가), 수행 -
-
maxVal
-
반환 -1
-
-
maxVal :=m[ch[i]]
-
-
c가 'c'와 같으면 -
-
(온도를 1 증가)
-
-
그렇지 않으면 c가 'k'와 같을 때 -
-
(온도 1 감소)
-
-
ret :=ret 및 temp의 최대값
-
-
initialize i :=1의 경우 i <5일 때 업데이트(i 1만큼 증가), −
-
m[ch[0]]이 m[ch[i]]와 같지 않으면 -
-
반환 -1
-
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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