[백준 13022] 늑대와 올바른 단어 [Java]

문제

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

 

---

풀이

주어진 문자열이 패턴 ‘wolf’으로 구성되는지 확인하는 문제다.

문자열의 길이는 50이므로 길이가 4배수인 패턴을 미리 생성하고 비교하거나 replace해주는 방식도 있지만, 정직(?)하게 풀어보았다.

우선 문자열의 시작은 ‘w’로 시작해야한다.

    static char[] ptn = "olf".toCharArray();

    private static boolean check(char[] S) {
        int idx = 0, gap = 0;
        while (idx < S.length) {
            if (S[idx] != 'w') {
                return false;
            }

그리고 ‘w’가 아닌 다른 문자가 나올 때 까지 연속된 ‘w’의 수를 세주자.

            while (idx < S.length && S[idx] == 'w') {
                ++gap;
                ++idx;
            }

연속된 ‘w’의 수만큼 패턴 ‘olf’가 유효한지 검증해주자.

만약 원본 문자열 S의 보다 길거나, gap만큼 패턴의 문자가 일치하지 않는다면 올바른 단어가 아니다.

            for (char ch : ptn) {
                for (int g = 0; g < gap; ++g) {
                    if (idx >= S.length || S[idx] != ch) {
                        return false;
                    }
                    ++idx;
                }
            }

이후 다시 gap을 0으로 초기화하고 다시 위 과정을 반복하면 된다. 탐색이 성공적으로 끝났다면 올바른 단어임을 의미한다.

            gap = 0;
        }
        return true;
    }

다양한 풀이가 존재해 재미있는 문제였다.

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/13022.java