14906번: 스러피 [JAVA]

문제 설명

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

14906번: 스러피

(https://www.acmicpc.net/problem/6493 또한 동일한 문제의 영어 버전이다.)

풀이

 주어지는 문자열의 조건이 단순 정규 표현식 만으로 표현하기에는 무리가 있다. 문제 속 '스럼프'에 대한 문자열 조건의 경우 쉽게 "(( D | E )F+)+ G" 라는 정규 표현식으로 표현이 가능하지만, '스림프'라는 문자열 조건은 일종의 재귀 표현이 조건에 들어가기 때문에, 자바의 정규 표현식으로는 이를 해결하기가 쉽지 않다.

 그래서 '스럼프' 판별에 대한 건 쉽게 Pattern을 사용하여 해결하고, '스림프' 판별에 대한 건 일종의 재귀 함수를 작성했다. 들어오는 문자열의 길이가 2라면 "AH"인지 아닌지, 문자열의 길이가 3이상이라면 해당 문자열이 "AB + 스림프 + C"인지 "A + 스럼프 + C"인지를 확인하고 맞다면 내부 '스림프'와 '스럼프'에 해당하는 문자열을 분리하여 다시 맞는 판별 함수를 호출하는 것으로 작성했다.

 그리고 들어오는 문자열의 '스러피' 판별을 위해서는 문자열을 2개로 분리해야 한다. 이 경우 사용한 조건으로는 스림프의 조건인데, 해당 조건에선 문자열의 끝이 'H'나 'C' 여야 한다. 이를 활용하여 문자열의 뒤에서부터 순차대로 조사해 가장 먼저 해당 알파벳이 나오는 곳을 기준으로 문자열을 분리해 앞 문자열이 '스림프'이고 뒷 문자열이 '스럼프' 인지를 판별하도록 함수를 호출한다.

 

public class Main {

    static int N;
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            String s1 = "", s2 = "";

            for (int j = s.length() - 1; j >= 0; j--) {//문자열 분리
                if(s.charAt(j)=='C'||s.charAt(j)=='H'){
                    s1 = s.substring(0, j + 1);
                    s2 = s.substring(j + 1);
                    break;
                }
            }

            if (isSlimp(s1) && isSlump(s2))//앞쪽은 '스림프'인지, 뒷쪽은 '스럼프'인지
                answer.append("YES\n");
            else
                answer.append("NO\n");
        }

        System.out.println("SLURPYS OUTPUT\n" + answer.toString() + "END OF OUTPUT\n");
    }

    public static boolean isSlimp(String s) {//'스림프' 판별 함수
        if(s.length()==0)
            return false;

        if (s.length() == 2) {
            if (s.equals("AH"))
                return true;
            else
                return false;
        }

        if (s.length() >= 3) {
            if(s.charAt(s.length()-1)!='C')
                return false;

            if(s.charAt(0)=='A' && s.charAt(1)=='B')
                return isSlimp(s.substring(2, s.length() - 1));

            if(s.charAt(0)=='A')
                return isSlump(s.substring(1, s.length() - 1));
        }

        return false;
    }

    public static boolean isSlump(String s) {//'스럼프' 판별 함수
        Pattern Slump = Pattern.compile("((D|E)F+)+G");

        return Slump.matcher(s).matches();
    }
}

결과