<백준> 문자열 폭발(Gold 4)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/9935 문자열 폭발 at main · heesoo-park/ForCodeKata

제출 결과

---

문제를 보면서 이거는 그냥 앞에서부터 훑으면서 체크한다면 숫자 제한이 1000000이기 때문에 무조건 시간초과가 나온다는 판단이 들었다.

그리고 일반 String으로 한다면 메모리도 초과할 거라고 판단했다.

그래서 스택이 떠올랐고 그대로 진행했다.

 

들어오는 문자가 폭발 문자열의 마지막 문자일 때까지 계속 스택에 문자를 넣다가 조건에 맞으면 폭발 문자열만큼 스택에서 문자를 빼서 뒤집은 다음에 폭발 문자열인지 체크를 했다.

뒤집은 이유는 스택에서 뺐기 때문에 순서가 거꾸로 되어있기 때문이다.

문자를 뺄 때는 StringBuilder를 사용했다.

그냥 String +연산으로 하니까 한 문자가 더해질 때마다 메모리를 추가적으로 사용하며 메모리 초과가 떴기 때문이다.

 

체크를 해서 같지 않으면 다시 스택에 집어넣고 같다면 그냥 다음 문자를 스택에 넣어줬다.

반복문 탈출 조건은 입력 문자열을 모두 돌았을 때로 했다.

결과 출력은 스택이 비어있지 않을 때는 아까처럼 StringBuilder를 사용했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val stack = Stack<Char>()
    
    val str = br.readLine()
    val target = br.readLine()
    
    var idx = 0
    while (true) {
        if (idx >= str.length) break
        
        stack.push(str[idx])
        if (target.last() == str[idx]) {
            var temp = StringBuilder()
            for (i in 0 until target.length) {
                if (stack.isNotEmpty()) temp.append(stack.pop())
            }
            
            val check = temp.reverse().toString()
            if (check != target) {
                for (i in 0 until check.length) {
                    stack.push(check[i])
                }
            }
        }
        
        idx++
    }
    
    if (stack.isNotEmpty()) {
        val sb = StringBuilder()
        for (i in 0 until stack.size) {
            sb.append(stack.pop())
        }
        println(sb.reverse().toString())
    } else {
        println("FRULA")
    }
}