문제 풀이
문자열, 스택
s = 폭발 문자열이 있는지 확인해야 하는 문자열
bomb = 폭발 문자열
end = 폭발 문자열의 마지막 문자
stack = 문자를 하나하나 저장하는 스택
index = 현재 스택에 문자가 저장된 마지막 인덱스, 스택에 들어간 문자 개수 - 1
s에서 문자를 하나하나씩 스택에 넣으면서 스택에 들어간 문자의 개수가 bomb의 길이 이상이면서 현재 넣은 문자가 폭탄 문자열의 마지막 문자일때 스택의 마지막에 들어갔던 문자를 bomb 길이만큼 비교해서 정확히 폭탄 문자열일때 스택에서 폭탄 문자열을 빼줌
그 결과로 스택에 폭탄 문자열을 제외한 문자열이 남아있음
index가 -1이라면 스택에 문자가 남지 않았으므로 FRULA 출력, 아니라면 스택에 남아있는 문자열 출력하면 정답
풀이 설명
문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 따라서 문자열에서 문자를 하나하나 확인하면서 폭발 문자열의 마지막 문자가 올 때 폭발 문자열인지 확인해 폭발 문자열이라면 제거하면 된다.
다만 폭발 문자열을 하나 발견할 때마다 폭발 문자열을 제외한 앞 뒤 문자열을 이어 붙여 새로운 문자열을 만들면 오래 걸리기 때문에 스택을 이용해 문자열에서 문자를 하나하나 넣으면서 폭발 문자열이 발견될때마다 스택에서 빼고 남은 문자들을 마지막에 문자열로 만들면 된다.
따라서 스택을 stack이라는 이름의 문자열 길이만큼의 문자 배열, 현재 문자가 들어간 인덱스를 나타내는 index, 폭탄 문자열 bomb, 폭탄 문자열의 마지막 문자 end를 정의하고 stack에 문자열 s의 문자 c를 하나하나씩 넣는다.
현재 스택에 들어간 문자의 개수 index + 1이 폭탄 문자열의 길이 bomb.length보다 크거나 같고 c가 end와 같을때 스택에 마지막에 들어간 문자열 stack[index - bomb.length + 1]부터 stack[index]까지가 폭탄 문자열 bomb과 일치하는지 확인해 일치한다면 index에서 bomb.length만큼 빼 폭탄 문자열을 스택에서 제거해준다.
이를 문자열 s의 모든 문자 c에 대해 확인하면 폭탄 문자열을 제거한 문자가 스택에 저장된다. 이 때 index를 확인해 -1 이라면 스택에 남은 문자가 없는 것이므로 FRULA를 출력하고, 아니라면 스택에 남은 문자를 문자열로 만들어 출력하면 정답이 된다.
소스 코드
fun main() = System.`in`.bufferedReader().run {
val s = readLine()
val bomb = readLine()
val end = bomb[bomb.length - 1]
val stack = CharArray(s.length)
var index = -1
for (c in s) {
stack[++index] = c
if (index + 1 >= bomb.length && c == end) {
var match = true
for (j in bomb.indices) {
if (stack[index - bomb.length + 1 + j] != bomb[j]) {
match = false
break
}
}
if (match) {
index -= bomb.length
}
}
}
val output = if (index == -1) "FRULA" else String(stack, 0, index + 1)
println(output)
}