시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 310 107 90 35.294%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

quqacukqauackck

예제 출력 1

2

예제 입력 2

kcauq

예제 출력 2

-1

예제 입력 3

quackquackquackquackquackquackquackquackquackquack

예제 출력 3

1

예제 입력 4

qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk

예제 출력 4

10

예제 입력 5

quqaquuacakcqckkuaquckqauckack

예제 출력 5

3

예제 입력 6

quackqauckquack

예제 출력 6

-1

힌트

예제 5의 경우에 다음과 같이 오리 3마리가 울었다고 할 수 있다.

  녹음: quqaquuacakcqckkuaquckqauckack
오리 1: ____q_u__a___ck_______________
오리 2: __q__u_ac_k_q___ua__ckq_u__ack
오리 3: qu_a_______c___k__qu___a_ck___

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013