[백준/Swift] 9935번: 문자열 폭발

 

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

9935번: 문자열 폭발

 

이 문제는 처음에는 쉽게... 문자열 메소드를 사용했다. 그랬더니 45-47에서 시간초과 발생...

//시간초과
while word.contains(explosion) && !word.isEmpty {
    word = word.replacingOccurrences(of: explosion, with: "")
}
print(word == "" ? "FRULA" : word)

그래서 다시 생각을 해보니,,, stack에 넣으면서 진행하면 될 것 같았다. word 문자열을 처음부터 다시 보지 않고 뒤의 suffix 부분만 비교해서 폭발 문자열이라면 빼버리면 되기 때문! 게다가 stack은 뒤에서만 작업하기 때문에 삭제 시간도 O(1)이다~

stack은 배열로 하지 않고 문자열로 해서 뒤에 붙였다. 맨 뒤 문자를 제거할 수 있는 removeLast() 메소드를 사용했다. 그리고 문자열의 hasSuffix() 메소드를 사용해서 맨 뒤의 부분 문자열이 폭발 문자열인지 확인해 주는 작업을 했다.

일단 폭발 문자열 explosion의 길이보다 stack의 길이가 작다면 패스해줬다. 폭발 문자열이 절대 아니니까! word의 모든 문자열을 순회했다면 while문을 끝내줬다. 그리고 빈문자열인지 확인하고 맞다면 FRULA 출력 아니면 stack 출력!

import Foundation

//input
let word = readLine()!.map{ String($0) }
let explosion = readLine()!
let explosionLength = explosion.count

//폭발 문자열이 없거나 남은 문자열이 없을 때까지 반복
var stack = ""
var count = 0
var i = 0
repeat {
    stack += word[i]
    count += 1
    i += 1
    if count < explosionLength { continue }
    if stack.hasSuffix(explosion) {
        stack.removeLast(explosionLength)
    }
} while i < word.count

print(stack == "" ? "FRULA" : stack)