[백준 14906] 스러피

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

14906번: 스러피

이번 문제는 정규식을 활용하기에 아주 좋은 문제라 생각하여 포스팅하였습니다.

 

문제

스러피(Slurpy)란 다음에서 설명할 어떠한 속성이 존재하는 문자열을 지칭한다. 문자열을 읽어서 스러피가 존재하는지를 판단하는 프로그램을 작성하라.

우선, 스럼프(Slump)는 다음 조건을 만족하는 문자열이다.

1. 첫 번째 문자가 ‘D’ 또는 ‘E’ 이다.
2. 첫 번째 문자 뒤에는 하나 이상의 ‘F’가 반복되어 연달아 나온다.
3. 위 2의 조건에서 반복되는 ‘F’ 뒤에는 또 다른 스럼프나 ‘G’가 온다. 따라서 항상 스럼프는 ‘F’ 끝에 오는 스럼프나 ‘G’로 끝난다. 예를 들어, DFFEFFFG는 첫 번째 문자가 ‘D’로 시작하고 두 개의 ‘F’가 연달아 나오며, 또 다른 스럼프 ‘EFFFG’로 끝난다. (똑같은 방식으로 ‘EFFFG’는 스럼프임을 알 수 있다)
4. 위의 경우가 아니면 스럼프가 아니다.

그리고 스림프(Slimp)는 다음 조건을 만족하는 문자열을 말한다.

1. 첫 번째 문자는 ‘A’이다.
2. 두개의 문자로만 된 스림프이라면 두 번째 문자는 ‘H’이다.
3. 세 개이상의 문자로 된 스림프라면 다음중 하나의 형식을 띈다.
   1. ‘A’ + ‘B’ + 스림프 + ‘C’
   2. ‘A’ + 스럼프 + ‘C’
4. 스림프는 길이 2이상이며, 위의 경우가 아니면 스림프가 아니다

마지막으로 스러피는 ‘스림프 + 스럼프’로 구성되는 문자열이라고 정의한다.

예를 들어,

• Slumps: DFG, EFG, DFFFFFG, DFDFDFDFG, DFEFFFFFG
• Not Slumps: DFEFF, EFAHG, DEFG, DG, EFFFFDG
• Slimps: AH, ABAHC, ABABAHCC, ADFGC, ADFFFFGC, ABAEFGCC, ADFDFGC
• Not Slimps: ABC, ABAH, DFGC, ABABAHC, SLIMP, ADGC
• Slurpys: AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFG
• Not Slurpys: AHDFGA, DFGAH, ABABCC
  입력
• 첫 번째 줄에는 입력될 문자열의 개수를 나타내는 정수 N이 1~10의 범위로 우선 입력된다. 다음 줄부터 N개의 문자열이 입력된다. 문자열은 1~60개의 알파벳 문자로 구성된다.
• 출력
• 첫 줄에는 “SLURPYS OUTPUT”을 출력한다. N개의 문자열 입력에 대해서 각 문자열이 스러피인지를 “YES” 또는 “NO”로 표기한다. 마지막으로 ‘END OF OUTPUT”를 출력한다.

 

풀이 과정

 

0. 정규식을 활용하여 문제를 해결해야겠다는 생각이 바로 듦

1. 스럼프와 스림프 2가지 유형에 대한 정규식이 필요

2. 스러피는 스림프 + 스럼프 이기때문에 문자열에 구간을 나누어서 2가지를 체크

3. 구현

 

순으로 진행했습니다.

 

이때 스럼프는 정규식 한번돌면 판단이 되는데 스림프 같은경우 케이스가 3개로 나누어서 처리해야했기 때문에

재귀가 필요했습니다.

 

 

코드

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.regex.Pattern

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val array = arrayListOf<String>()
    for (i in 0..N - 1) {
        val input = br.readLine()
        array.add(input)
    }
    println("SLURPYS OUTPUT")
    for (i in 0..N - 1) {
        val input = array[i]
        var res = false
        for (j in 2..input.length - 3) {
            val slumpStr = input.substring(0, j)
            val slimpStr = input.substring(j, input.length)
            if (isSlimp(slumpStr) && isSlump(slimpStr)) {
                res = true
                break
            }
        }
        if (res) {
            println("YES")
        } else {
            println("NO")
        }
    }
    println("END OF OUTPUT")
}

fun isSlump(str: String): Boolean {
    val reg = "^((D|E)(F)+)+(G)$"
    return Pattern.matches(reg, str)
}

fun isSlimp(str: String): Boolean {
    if (str.length > 3) {
        if (Pattern.matches("(AB)\\w+(C)$", str)) {
            val input = str.substring(2, str.length - 1)
            return isSlimp(input)
        } else if (Pattern.matches("(A)\\w+(C)$", str)) {
            val input = str.substring(1, str.length - 1)
            return isSlump(input)
        }

    } else {
        if (str == "AH") return true
    }
    return false
}