[Swift] 백준_문자열 폭발(9935)

문제

 

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

9935번: 문자열 폭발

 

 

풀이

 

처음 방법(비효율적)

 

처음에 풀었던 방법은 입력된 문자열에서 removeLast()로 원소를 스택에 추가한 뒤, 스택의 size가 폭발 문자열의 count와 동일할 때 매번 검사를 해주도록 구현하였다. 

 

removeLast()로 받다보니 reversed()를 이용해서 다시 뒤집어야했고, 관련이 없는 문자열이 들어올때도 size만 맞으면 검사를 해야했다. 시간초과가 나오지는 않고 통과는 되었지만 굉장히 비효율적인 방법이었다.

var word = readLine()!.map { String($0) }
let bomb = readLine()!.reversed().map { String($0) }
let bombCount = bomb.count
var stack: [String] = []
var result: [String] = []

for _ in 0..<word.count {
    stack.append(word.removeLast())
    while stack.count >= bombCount && Array(stack[stack.count-bombCount...stack.count-1]) == bomb {
        for _ in 0..<bombCount {
            stack.removeLast()
        }
    }
}
if stack.isEmpty {
    print("FRULA")
} else {
    if stack == bomb {
        print("FRULA")
    } else {
        print(stack.reversed().joined())
    }
}

 

 

두번째 방법

 

문자열을 앞에서부터 하나씩 스택에 넣고, 들어온 문자가 폭발 문자열의 마지막 문자와 같은 경우에만 검사를 하도록했다. 이때 인덱스를 이용해 문자열을 확인하므로 스택의 size가 폭발 문자열의 길이보다 큰지 확인해야했다. 

만약 스택의 size가 더 크다면, 스택의 마지막 원소부터 폭발 문자열 길이만큼이 폭발 문자열과 동일한지 확인하도록 하였다. 

 

속도가 거의 네 배 빨라졌다.

import Foundation

let word = readLine()!
let bomb = readLine()!.map { $0 }
var stack: [Character] = []

for char in word {
    stack.append(char)
    if char == bomb.last! && stack.count >= bomb.count && Array(stack[stack.count - bomb.count...stack.count-1]) == bomb {
        for _ in 0..<bomb.count {
            stack.removeLast()
        }
    }
}
if stack.isEmpty {
    print("FRULA")
} else {
    print(stack.map { String($0) }.joined())
}

 

 

_____________________________________________________________________________________________________

 

비효율적이라고 생각이 들면 다르게 생각해보자.