[백준] 12933. 오리 (Java)

[BOJ] 12933. 오리

📌 풀이 과정

String quack = "quack"; // "quack"의 순서에 해당하는 문자열

quack 순서를 나타내는 문자열의 인덱스는 0부터 4까지이며
각 인덱스는 q=0, u=1, a=2, c=3, k=4를 의미

List<Integer> ducks = new ArrayList<>(); // 오리의 상태를 저장하는 리스트

오리 상태를 저장하는 리스트는 각 오리가 "quack"에서 어디까지 소리를 냈는지를 가리킨다.
리스트의 각 원소는 오리의 현재 상태를 나타내며, 다음에 와야 하는 문자의 인덱스를 저장한다.

예를 들어

• ducks = [1]: 첫 번째 오리는 'q'를 말했고, 이제 'u'를 말해야 함.
• ducks = [2, 1]: 첫 번째 오리는 'u'까지 말했고, 이제 'a'를 말해야 함. 두 번째 오리는 'q'를 말했고, 이제 'u'를 말해야 함.
• ducks = [0, 0]: 두 마리의 오리 모두 "quack"을 완성했고, 다시 새로운 울음을 시작할 수 있는 상태.

각 오리가 'quack'의 어느 단계에 있는지를 추적하여 문제를 해결하는 방식이다.

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * 12933. 오리
 * 메모리: 14612 KB
 * 시간 : 116 ms
 */
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"; // "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;

                    // 오리가 "quack"을 완료하면 상태 초기화
                    if (ducks.get(i) == 5) {
                        ducks.set(i, 0);
                    }
                    break;
                }
            }

            // 기존 오리들이 처리하지 못한 소리라면 새로운 오리 추가
            if (!found) {
                if (c == 'q') {
                    ducks.add(1); // 새로운 오리는 'q'로 시작
                    count = Math.max(count, ducks.size()); // 최대 오리 수 기록
                } else {
                    System.out.println(-1);
                    return;
                }
            }
        }

        // 모든 오리가 제대로 "quack"을 완료했는지 확인
        for (int state : ducks) {
            if (state != 0) {
                System.out.println(-1);
                return;
            }
        }

        System.out.println(count);
    }
}

---

🧐 다른 풀이

다른 사람들은 어떻게 풀었는지 궁금해서 찾던 중 신박했던 풀이가 꽤나 있었다.
백준 12933번 : 오리 | 자바 풀이

사실 나도 quack 배열의 인덱스에 해당하는 상태의 갯수를 조절하여 관리하는 방법을 떠올렸지만
어떻게 순서를 보장하지? 했었는데 이 코드를 보고 깨달았다.

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));
        String str = br.readLine();
        int[] arr = new int[6];
        int size = str.length();
        int max = 0;
        arr[0] = size;

        for(int i = 0; i < size; i++) {
            int n = 0;
            if(str.charAt(i) == 'q') n = 1;
            if(str.charAt(i) == 'u') n = 2;
            if(str.charAt(i) == 'a') n = 3;
            if(str.charAt(i) == 'c') n = 4;
            if(str.charAt(i) == 'k') n = 5;
            if(arr[n-1] == 0) {
                System.out.println("-1");
                return;
            }
            arr[n]++;
            arr[n-1]--;
            max = Math.max(max, arr[1]+arr[2]+arr[3]+arr[4]);
        }

        if(arr[5] * 5 != size) {
            System.out.println("-1");
            return;
        }
        System.out.println(max);
    }
}

이 풀이에서 arr[] 배열이 각 단계에서 현재 처리 중인 "quack" 상태를 저장하는 배열이다.

arr[0]: 아직 시작되지 않은 문자 수
arr[1]: ‘q’를 말한 오리 수
arr[2]: ‘u’를 말한 오리 수
arr[3]: ‘a’를 말한 오리 수
arr[4]: ‘c’를 말한 오리 수
arr[5]: ‘k’를 말한 오리 수

‘u’는 ‘q’가 나와야 하고(arr[0]에 남은 값이 있어야 함),
‘a’는 ‘u’가 있어야 하며,
‘c’는 ‘a’가 있어야 하며,
‘k’는 ‘c’가 있어야 한다.

각 문자에 대한 이전 상태가 arr[n-1]에서 0보다 큰지 확인한다.
만약 이전 상태가 없으면 순서가 잘못된 것으로 간주하고 -1을 출력한다.