[자바] 백준 12933 - 오리 (java)

 문제 : boj12933

---

 

필요 알고리즘 개념

• 그리디
  
  • 찾을 수 있는 오리를 한마리씩 모두 찾아주는 규칙을 취하면 더 쉽게 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  문제 이해가 다소 어려울 수 있는 문제이다. 사실 문제만 이해 잘 하면 그리 어렵지 않게 풀 수 있다. 그러니 여러 예시를 보면서 문제를 잘 이해해보자.

 

  만약 '오리의 최대 마리수'를 찾는다고 생각해보자. 그럼 quackquackquack 에 대해 각 소리를 1마리씩 냈다고 생각해서 3마리로 생각할 수 있다.

 

  하지만 이 문제에서는 '오리의 최소 마리수'를 찾고자 하는것이므로, 여러 quack을 한 마리가 낼 수 있었다면 1마리로 칠 수 있다. 즉, quackquackquack 에 대해 한마리가 연속으로 3번 낼 수 있는 것이므로 1마리로 치면 된다. 이처럼 '최소 마리수'의 관점에서 문제를 이해하면 된다. 그럼 이하 몇가지 예시를 보자.

 

quackquackquack -> 3번 났지만 '최소'이고 한마리가 낼 수 있으므로 1마리
qquackuack -> 오리는 무조건 quack 순서로 내므로 이건 2마리가 필요하다.
qqauckuack -> quack 하나는 가능한데, 나머지 한번은 qauck가 된다. 이건 오리가 울 수 있는 소리가 아니니 녹음이 올바르지 않은 경우이다.
quackqquuaacckk -> 처음 quack 이후 quack가 겹치는데, 그 중 한마리는 처음 quack랑 같은녀석으로 칠 수 있다. 그러니 2마리이다.

 

---

 

  그럼 이걸 어떻게 구현할 수 있을까? 매번 한마리씩 소리를 낼 수 있는 경우를 제외시켜보면 어떨까? 예를들어서 quackquack에 대해서

 

1. qquackuack -> 우선 첫번째 오리가 울 수 있는걸 뺀다.

2. 그럼 quack이 남는다.

3. 이제 다음 오리가 울 수 있는걸 뺀다.

4. 그럼 아무것도 안남는다. -> 그러니 2마리이다.

 

  이 때, 문자열의 길이는 최대 2500이고 오리는 항상 quack 으로 5개의 문자로 울어야 하므로 존재 가능한 최대 오리는 500마리이다. 500마리에 대해 매번 자기가 울 수 있는 부분을 빼낸다고 치면, O(500*2500) 이면 된다. 그러므로 오리 한마리 한마리에 대해 모든 문자열을 보면서 찾아내도 시간 내에 통과 가능하므로 이렇게 하면 된다.

 

  내 경우엔 각 오리가 울 수 있을 때마다 해당 문자를 q,u,a,c,k가 아닌 문자로 변경해줬다. 예를들어 'X'로 변경한다고 치고, qqquuuaaaccckkk에 대해 보자.

 

1. 첫번째 오리 확인 후 XqqXuuXaaXccXkk

2. 두번째 오리 확인 후 XXqXXuXXaXXcXXk

3. 세번째 오리 확인후 XXXXXXXXXXXXXXX

 

  그리고 남은 문자열에 X가 아닌 문자가 존재한다면 (남는 q,u,a,c,k가 존재한다면) 녹음이 올바르지 않은 경우가 된다. 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final char[] QUACK = {'q','u','a','c','k'};
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = br.readLine().toCharArray();
        if (arr.length%5 != 0) {
            System.out.println(-1);
            return;
        }
        int remain = arr.length;
        int cnt = 0;
        while (remain != 0) {
            int pt = 0;
            int idx = 0;
            boolean chk = false;
            int[] tmp = new int[5];
            while (idx < arr.length) {
                if (arr[idx]==QUACK[pt]) {
                    tmp[pt++] = idx;
                    if (pt==5) {
                        chk = true;
                        remain-=5;
                        pt=0;
                        for (int i = 0; i < 5; i++) arr[tmp[i]] = '\0';
                    }
                }
                idx++;
            }
            if (chk) cnt++;
            else break;
        }
        System.out.println(remain==0?cnt:-1);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}