[백준 / 골드4] 문자열폭발 with kotlin

문자열 폭발

 

풀이 과정 

처음에 풀이를 진행했을 때 단순하게 replace를 사용하였다 ->  문제 조건 : 문자열의 최대 크기가 1000000이었고,

계속해서 최대 길이의 문자열을 만들어내야 함으로 메모리 초과가 발생하였다

스택을 이용하여 풀이를 진행하였다. 

package com.chanhue.algorithm.백준.골드


fun main(){




    val s = readLine()!!       // 원본 문자열 입력
    val bomb = readLine()!!    // 폭발 문자열 입력

    // 스택으로 사용할 MutableList 생성
    val stack = mutableListOf<Char>()
    // 원본 문자열의 각 문자를 순회하며 스택에 push

    for(c in s){
        stack.add(c)
        // 스택에 있는 마지막 bombLength 개의 문자와 폭발 문자열이 일치하는지 검사

        if(stack.size>=bomb.length){
            var isBomb=true
            for(i in 0 until bomb.length){
                if(stack[stack.size-bomb.length+i]!=bomb[i]){
                    isBomb=false
                    break
                }
            }
            // 폭발 문자열이 완전히 일치하면, 해당 부분(마지막 bombLength 문자들)을 스택에서 pop

            if(isBomb==true){
                for (i in 0 until bomb.length) {
                    stack.removeAt(stack.lastIndex)
                }
            }
        }
    }
    // 스택이 비어있다면 모든 문자가 폭발한 것이므로 "FRULA" 출력
    if (stack.isEmpty()) {
        println("FRULA")
    } else {
        // 스택에 남은 문자들을 순서대로 이어 붙여 결과 문자열 생성 후 출력
        println(stack.joinToString(""))
    }





}