[ BOJ ][JAVA][12933] 오리

www.acmicpc.net/problem/12933

12933번: 오리

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	530	188	155	36.215%

문제

오리의 울음 소리는 "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

코드

/*
    오리는 꽥꽥
    quack 문자를 미리 만들어 input 값에서 q를 방문했으면 index를 증가시키고 다음 문자를 비교하도록 한다.
*/

import java.util.*;
import java.io.*;
public class p12933 {
    static String quack = "quack";
    static int len = quack.length();
    static int cnt = 0;
    static boolean[] visit;
    static String duck = "";
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        duck = br.readLine();
        visit = new boolean[duck.length()];

        if (duck.length() % 5 != 0) {
            System.out.println(-1);
            return;
        }

        for (int i = 0; i < duck.length(); i++) {
            if (duck.charAt(i) == 'q' && !visit[i]) {
                go(i);
            }
        }

        for (int i = 0; i < duck.length(); i++) {
            if (visit[i] == false) {
                System.out.println(-1);
                return;
            }
        }

        if (cnt == 0) {
            System.out.println(-1);
            return;
        }

        System.out.println(cnt);

    }
    static void go(int start) {
        int j = 0;
        boolean first = true;
        for (int i = start; i < duck.length(); i++) {
            if (duck.charAt(i) == quack.charAt(j) && !visit[i]) {
                visit[i] = true;
                if (duck.charAt(i) == 'k') {
                    if (first) {
                        cnt++;
                        first = false;
                    }
                    j = 0;
                    continue;
                }
                j ++;
            }
        }
    }
}