문제
오리가 quack 소리로 운다고 합니다. 오리가 우는 소리가 문자열로 주어질 떄, 최소한 몇 마리의 오리가 있는지 찾는 문제입니다.
예제 1.
quackquack
-> 1예제 2.
quqacukqauackck
-> 2예제 3.
kcauq
-> -1예제 4.
녹음: quqaquuacakcqckkuaquckqauckack
오리 1: ____q_u__a___ck_______________
오리 2: __q__u_ac_k_q___ua__ckq_u__ack
오리 3: qu_a_______c___k__qu___a_ck___
-> 3접근 방식
오리가 우는 소리는 quack로 순서대로만 웁니다. 현재 어느 울음 소리인지 인덱스를 기록할 필요가 있을 것으로 생각하며, 이를 저장할 변수가 필요하다고 판단했습니다.
그래서 처음에는 스택으로 q, u... 순서대로 들어오는 것들을 저장하면 되지 않을까 싶었는데 어짜피 모두 q, u... 순서이기 때문에 정수인 인덱스만 저장하기로 했습니다.
- 예시
| 오리 | 울음 인덱스 |
|---|---|
| 0번 오리 | 0 ( 현재 울지 않음 ) |
| 1번 오리 | 3 ( c를 의미 ) |
| 2번 오리 | 1 ( u를 의미 ) |
그리고 문제에서는 최소 오리 개수를 구해야 하므로 이전에 울었던 오리도 다시 울 수 있습니다. 그래서 울음을 그친 오리(저장된 인덱스가 0)가 있다면 해당 오리의 울음 인덱스를 증가시킴으로 울음 인덱스를 저장하도록 했습니다.
풀이
오리별로 현재 울음소리 인덱스를 저장해야 합니다. 그래서 vector나 map으로 오리들을 저장해야 합니다. 개인적으로는 간편하게 새 값을 넣을 수 있고 순서가 자동으로 정렬되는 map을 선택했습니다.
-
울음소리에 적합한 오리 찾기
- a. 울음소리에 적합한 오리가 있다면 해당 오리의 울음 인덱스 증가
- b. 없다면, 잘못된 울음소리로 판단
-
울음소리가 끝났는데 아직 덜 운 오리가 있는지 확인
-
총 오리 개수 반환
코드
map<char, int> duckCrying; // quack를 0 ~ 4 인덱스로 매핑
string str; // 주어진 울음소리
map<int, int> ducks; // 오리들 울음 인덱스 저장
void init() {
duckCrying['q'] = 0;
duckCrying['u'] = 1;
duckCrying['a'] = 2;
duckCrying['c'] = 3;
duckCrying['k'] = 4;
}
int sol() {
int cnt = 0; // 현재 오리 개수
for (int i = 1; i < str.length(); ++i) {
bool isAdded = false; // 새로운 울음소리가 들어갔는지
for (int id = 0; id < cnt; ++id) { // 해당 울음소리가 알맞는 오리 찾기
if (duckCrying[str[i]] == ducks[id]) {
isAdded = true;
ducks[id]++;
if (ducks[id] == 5) { // 끝난 경우
ducks[id] = 0; // 오리 대기 상태
}
break;
}
}
if (!isAdded && str[i] == 'q') { // 만약 못 찾았는 데 q이면 새로운 오리 추가
ducks[cnt]++;
cnt++;
isAdded = true;
}
if (!isAdded) { // 잘못된 울음소리
return -1;
}
}
for (int id = 0; id < cnt; ++id) {
// 울움소리 종료 되었는데 아직 덜 운 오리가 있는 경우, 잘못된 울음 소리
if (ducks[id] != 0) return -1;
}
return cnt;
}
int main() {
cin >> str;
init();
cout << sol();
}