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

출처: unsplash.com

 

문자열 폭발(9935번)

Gold 4

#자료 구조 #문자열 #스택

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

 

문제 내용

 

 

문제 접근

첫 번째 줄의 문자열에서 두 번째 문자열이 존재하지 않을 때까지 문자열을 제거한 결과를 출력하는 문제.

문자열이 제거되고 남은 문자열들은 서로 붙어서 새 문자열이 된다.

 

단순히 문자열을 확인해 보면서 문자열을 제거해 나가면 되는 간단한 문제이다.

그래서 일단은 replace를 반복시켜서 진행해 보았다.

while (true) {
    val replaceRes = string.replace(removeStr, "")
    if (replaceRes != string) string = replaceRes
    else break
}

결과는 메모리 초과, 애초에 replace만으로 풀리는 걸 기대하지도 않았기 때문에 다음 방법을 사용했다.

 

다음으로 알고리즘 분류에 있는 스택을 사용해 보았다.

stack에 문자를 하나씩 넣으면서 폭발시켜야 할 문자열이 있으면 stack에서 그 값을 제거하는 방식으로 구현해 보았다.

val stack = Stack<String>()

for (i in string.indices) {
    stack.add(string[i])
    if (string[i] == boomString.last().toString() && stack.size >= boomString.length) {
        var subRes = ""
        for (j in stack.lastIndex downTo stack.lastIndex - boomString.lastIndex) {
            subRes += stack[j]
        }

        if (subRes == boomString.reversed()) {
            for (j in boomString.indices) stack.pop()
        }
    }
}

이 코드도 메모리 초과가 발생했다.

그래서 위의 stack 방식과 유사하게 구현이 가능하면서 메모리 절약도 가능한 stringBuilder로 구현을 시도했다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val string = readLine()
    val boomString = readLine()
    val sb = StringBuilder()
    var subRes: String

    for (i in string.indices) {
        sb.append(string[i])
        if (string[i] == boomString.last() && sb.length >= boomString.length) {
            subRes = sb.substring(sb.lastIndex - boomString.lastIndex, sb.length)
            if (subRes == boomString) {
                sb.delete(sb.lastIndex - boomString.lastIndex, sb.length)
            }
        }
    }

    if (sb.isEmpty()) println("FRULA")
    else println(sb)
}

 

문제 풀이

우선 계속 stringBuilder에 문자를 집어넣는다.

현재 stringBuilder의 길이가 폭발 문자열보다 길거나 같으면서 집어넣는 문자열이 폭발 문자열의 마지막 문자와 같으면 폭발 문자열의 길이만큼 앞의 문자들을 확인한다.

확인한 문자가 폭발 문자열과 동일하면 그 문자들을 지워준다.

 

그러면 위와 같은 입력이 주어졌을 때,

aaaaabbbbb
ab

sb에는 a가 다 들어가고 b가 들어올 차례가 된다면 폭발 문자열인 ab와 동일한 값들을 삭제해 나갈 것이다.

그러면 정답은 빈 문자열이기 때문에 FURLA가 출력된다.

 

 

문제 해결 과정

2가지의 방법을 시도했다.

replace를 이용하는 방법은 애초에 기대도 안 했다. 골드 문제인데 이리 쉽게 풀릴 리가 없기 때문이다. 역시나 40%대에서 메모리 초과가 나왔다.

stack을 이용하는 방법은 문자열이 길어지면 잡아먹는 메모리가 커져서 메모리 초과가 뜨는 듯했다. 최적화를 한다면 풀 수 있을지도 모르겠다.

내 기준에 체감 난이도는 실버 2~실버 1인 듯하다.

구현에 크게 어려움을 느끼지 않았다.

stack 대신에 stringBuilder를 쓰는 게 더 메모리 관리가 편하다는 것을 알게 되었으니 좋다.