[백준 JAVA] 12933 오리

12933 오리

https://www.acmicpc.net/problem/12933

문제설명

"quack"이라는 소리를 내는 오리의 개수를 구한다.

문자열에는 'q', 'u', 'a', 'c', 'k'가 순서대로 포함되어야 하며, 각 오리는 "quack" 소리를 한 번 내면 모든 문자를 사용해야 한다.

또한, 주어진 문자열은 유효한 오리 소리의 연속이어야 하며, 하나의 오리가 "quack" 소리를 내고 있는 동안

다른 오리들이 그 소리를 중복하지 않고 내는 방식도 고려한다.

접근방식

O(N * D) 시간복잡도

• N은 입력 문자열의 길이이다.
• D는 소리를 내고 있는 오리의 최대 개수이다. (리스트의 크기)

실제로 D는 "quack" 소리를 내기 위한 문자가 순차적으로 완성되어야 하므로, 일반적으로 D는 O(N/5)로 제한된다.

• 모든 문자에 대해 각 오리의 상태를 검사해야 할 수 있으므로, O(N * D)라는 복잡도를 가진다.

문제 조건 분석 과정

 

• 입력 검증:
  • 문자열이 'q'로 시작하지 않거나, 문자열의 길이가 5의 배수가 아니면 -1을 출력한다.
  • "quack" 소리는 5개 문자로 구성된다.
• 오리 소리 상태 관리:
  • 리스트를 만들어 현재 소리를 내고 있는 오리들을 저장한다.
  • 각 오리는 "quack" 소리의 각 문자를 몇 번 냈는지를 계산한다.
  • 문자열의 각 문자를 순회하면서 해당 문자가 오리의 소리와 맞는지를 검사한다.
  • 만약 문자가 'q'라면 새로운 오리를 추가하고,
  • 그렇지 않다면 기존의 오리 중에서 해당 문자를 소리 내고 있는 오리를 찾아 상태를 업데이트한다.
• 소리 완성 여부 확인:
  • 모든 오리의 소리가 완전히 끝났는지를 확인하기 위해, ducks 리스트의 모든 상태가 0인지 확인한다.
  • 그렇지 않으면 -1을 출력한다.

 

전체코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] input = br.readLine().toCharArray();

        String quack = "quack";
        List<Integer> ducks = new ArrayList<>();
        int count = 0;

        if (input[0] != 'q' || input.length % 5 != 0) {
            System.out.println(-1);
            return;
        }

        for (char c : input) {
            boolean found = false;

            for (int i = 0; i < ducks.size(); i++) {
                if (quack.charAt(ducks.get(i)) == c) {
                    ducks.set(i, ducks.get(i) + 1);
                    found = true;

                    if (ducks.get(i) == 5) {
                        ducks.set(i, 0);
                    }
                    break;
                }
            }

            if (!found) {
                if (c == 'q') {
                    ducks.add(1);
                    count = Math.max(count, ducks.size());
                } else {
                    System.out.println(-1);
                    return;
                }
            }
        }

        for (int state : ducks) {
            if (state != 0) {
                System.out.println(-1);
                return;
            }
        }

        System.out.println(count);
    }
}