[알고리즘] 백준 12933 - 오리

1. 문제

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

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

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

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

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

2. 입력

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

3. 풀이

1. 예제

• quqacukqauackck
  출력 : 2
• quackqauckquack
  출력 : -1
• quqaquuacakcqckkuaquckqauckack
  출력 : 3
• qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk
  출력 : 10

2. 풀이

오리 울음소리가 아닌 경우

• 울음소리 글자수가 5의 배수가 아닐 때
• 울음소리 글자수가 5이하일 때
• 울음소리 첫 글자가 q로 시작하지 않을 때
• 한 오리의 울음소리가 k로 끝나지 않을 때

주의점

틀린 경우가 하나라도 있으면 올바르지 않은 경우라 -1을 출력해야 한다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class duck_12933 {
    public static void solution() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String sound = bf.readLine();

        if(sound.length()%5!=0 || sound.length()<5 || sound.charAt(0)!='q'){
            System.out.println("-1");
            return;
        }

        HashMap<Integer,Character> list = new HashMap<>();
        int count = 0;

        boolean noduck = false;
        boolean needNew = false;
        boolean isPut = false;

        for(int i=0;i<sound.length();i++){
            if(i==0 && sound.charAt(i)=='q'){
                needNew = true;
            }

            for(int j = 1;j<=count;j++){
                if(list.containsKey(j)){
                    switch (sound.charAt(i)){
                        case 'q':
                            if(list.get(j)=='k'){
                                list.put(j,'q');
                                noduck = false;
                                needNew = false;
                                isPut = true;
                            }
                            else{
                                noduck = false;
                                needNew = true;
                                continue;
                            }
                            break;
                        case 'u':
                            if(list.get(j)=='q'){
                                list.put(j,'u');
                                noduck = false;
                                isPut = true;
                            }
                            else{
                                noduck = true;
                            }
                            break;
                        case 'a':
                            if(list.get(j)=='u'){
                                list.put(j,'a');
                                noduck = false;
                                isPut = true;
                            }
                            else{
                                noduck = true;
                            }
                            break;
                        case 'c':
                            if(list.get(j)=='a'){
                                list.put(j,'c');
                                noduck = false;
                                isPut = true;
                            }
                            else{
                                noduck = true;
                            }
                            break;
                        case 'k':
                            if(list.get(j)=='c'){
                                list.put(j,'k');
                                noduck = false;
                                isPut = true;
                            }
                            else{
                                noduck = true;
                            }
                            break;
                    }
                    if(isPut){
                        isPut = false;
                        break;
                    }
                }

            }

            if(noduck){
                System.out.println("-1");
                return;
            }
            else if(needNew){
                list.put(++count,'q');
                needNew = false;
            }

/*
            for(int k= 1;k<=count;k++){
                System.out.println(k+" "+list.get(k));
            }
            System.out.println();

 */
        }

        for(int i=1;i<count;i++){
            if(list.get(i)!='k'){
                System.out.println("-1");
                return;
            }
        }

        System.out.println(list.size());
    }
}