백준 [9935] kotlin

fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    var s = br.readLine().toString()
    e = br.readLine().toString()

    while(true){
        val tmp = s
        s = s.split(e).joinToString("")
        if(tmp == s) break
    }
    if(s == "") bw.write("FRULA")
    else bw.write(s)
    bw.flush()
    bw.close()
}

[문제]

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

9935번: 문자열 폭발

[풀이]

<잘못된 풀이>

처음에는 split을 이용하여, 문자열을 제거하여, 더 이상 줄지 않으면 출력하는 방식으로 쉽게 풀려고 했다.

fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    var s = br.readLine().toString()
    e = br.readLine().toString()

    while(true){
        val tmp = s
        s = s.split(e).joinToString("")
        if(tmp == s) break
    }
    if(s == "") bw.write("FRULA")
    else bw.write(s)
    bw.flush()
    bw.close()
}

하지만, 당연히 메모리 초과가 발생했다.

그 이유는 예를 들어 aaabbbb가 주어진 문자열이고, 폭발 문자열이 ab라고 하면 위의 코드로 풀게되면 중간에서 ab가 반복적으로 제거가 된다. 주어진 문자열의 길이는 100만이므로, 100만번의 split과 join하는 과정이 반복되어 메모리 초과가 발생했다.

 

<정답 풀이>

다르게 해결한 풀이는 Stack을 사용하는 것이다.

문자열을 Stack에 하나씩 넣으면서, 만약 Stack의 크기가 폭발 문자열보다 크거나 같게 되면,

 

스택의 뒤부터 폭발 문자열부터 비교하여, 폭발 문자열과 일치하면 제거를 한다.

aaabbbb의 경우로 예를 들면 

스택에 a,a,a,b가 들어오면 a,b가 존재하므로 a, b를 제거한다.

그러면 a,a가 남게되고 다음에 b가 들어오게 되면 a,b가 제거가 된다.

 

stack을 이용하여 끝에서부터 확인을 하므로 O(n)과정으로 탐색이 가능하기에 오류가 나지 않는다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.Stack

fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    var s = br.readLine().toString()
    var e = br.readLine().toString()

    var boombsize = e.length
    var stack = Stack<Char>()
    for(i in s.indices)
    {
        stack.push(s[i])
        if(stack.size >= boombsize){
            var tmpstack = Stack<Char>()
            var idx = boombsize - 1
            while (idx >= 0 && stack.peek() == e[idx]){
                tmpstack.push(stack.pop())
                idx--
            }
            if(tmpstack.size < boombsize) {
                while (tmpstack.isNotEmpty()){
                    stack.push(tmpstack.pop())
                }
            }
        }
    }
    if(stack.isEmpty()) bw.write("FRULA")
    else bw.write(stack.toCharArray())
    bw.flush()
    bw.close()
}