[백준 9935번][Kotlin] 문자열 폭발

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

9935번: 문자열 폭발

 

난이도 : 골드 4
태그 : 자료구조, 스택, 문자열

 

 

설명

 

문제의 지문에 문자열의 길이는 1~1,000,000 로 명시되어 있습니다.

 

가장 쉽게 풀 수 있는 방법은 replaceAll 메소드를 사용하는 것 이겠지만,

문자열의 길이를 보니 시간초과, 메모리 초과 등이 날 것이 당연하네요.

 

따라서, 저는 Stack 자료구조를 사용하여 해당 문제를 풀이하였습니다.

 

스택에 하나씩 문자열을 push 할 때마다,

스택의 마지막쪽 문자열과 폭탄 문자열을 비교하며,

같은 문자열일 경우 pop을 합니다.

 

 

소스코드

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val line = br.readLine()
    val boom = br.readLine()

    val boomLen = boom.length

    val stack = Stack<Char>()

    for (ch in line) {
        stack.add(ch)

        // 스택의 길이가 boom의 길이보다 클 때만
        if (stack.size >= boomLen) {
            var isEqual = true

            // 스택의 마지막 boomLen 만큼의 크기의 문자열과 boom 문자열 비교
            for (i in 0 until boomLen) {
                if (stack[stack.size - boomLen + i] != boom[i]) {
                    isEqual = false
                    break
                }
            }

            if(isEqual) {
                repeat(boomLen) {
                    stack.pop()
                }
            }
        }
    }
    val sb = StringBuilder()

    if (stack.isEmpty()) print("FRULA")
    else {
        stack.forEach { sb.append(it) }
        println(sb.toString())
    }
}

 

문자열 비교

for (ch in line) {
    stack.add(ch)

    // 스택의 길이가 boom의 길이보다 클 때만
    if (stack.size >= boomLen) {
        var isEqual = true

        // 스택의 마지막 boomLen 만큼의 크기의 문자열과 boom 문자열 비교
        for (i in 0 until boomLen) {
            if (stack[stack.size - boomLen + i] != boom[i]) {
                isEqual = false
                break
            }
        }

        if(isEqual) {
            repeat(boomLen) {
                stack.pop()
            }
        }
    }
}

문자열 한글자씩 스택에 add 합니다.

 

이후, 스택의 길이가 폭탄 문자열의 상태보다 클때,

스택의 마지막 부분과 폭탄의 문자열을 비교합니다.

 

만약, 문자열이 같을 경우 폭탄 문자열의 길이만큼 스택에서 꺼냅니다(pop).

 

 

 

남은 문자열 출력

val sb = StringBuilder()

if (stack.isEmpty()) print("FRULA")
else {
    stack.forEach { sb.append(it) }
    println(sb.toString())
}

마지막으로 스택에 아무것도 없으면 FRULA를,

스택에 원소가 남아있으면 스택 내 원소를 출력합니다.

 

여기서 주의할 점은, 반복문을 이용해 스택 내 원소 하나하나를 print()하면 시간초과가 발생하기 때문에

StringBuilder로 출력해야 시간초과 없이 출력할 수 있습니다.

 

저는 출력부분에서 시간초과가 나는줄도 모르고

애꿎은 문자열 비교 로직만 자꾸 만지작 만지작 거렸네요...

 

 

 

후기

이와 비슷한 문제들을 몇번 푼 적 있었기에,

아이디어와 구현은 쉽게쉽게 했으나,

마지막 출력부분에서 for문으로 스택 내 원소를 하나하나 출력하는 바람에

시간초과가 발생해 꽤 어리둥절했던 문제였습니다.

 

혹시..? 하는 마음에 StringBuilder로 문자열을 합쳐서 출력을 했는데 통과하더군요.

역시 코딩할때엔 혹시...? 하는 마음으로 코딩을 해야 하나 봅니다.