문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
풀이
폭발 문자열이 나타날 때마다 바로 지워야 하므로, 전체 문자열을 계속 다시 탐색하면 비효율적이다. 문자를 하나씩 보면서 스택처럼 쌓고, 뒤쪽이 폭발 문자열과 같아지는 순간만 잘라내는 방식이 핵심이다.
코드에서는 결과 버퍼에 현재 문자를 추가한 뒤, 길이가 충분해졌을 때 끝부분이 폭발 문자열과 일치하는지 확인한다. 맞으면 그 길이만큼 제거하고 계속 진행한다.
지금 막 새로 만들어진 접미사만 검사하면 충분하다는 점이 핵심이다.
코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String bomb = br.readLine();
System.out.println(solve(input, bomb));
}
private static String solve(String input, String bomb) {
StringBuilder sb = new StringBuilder();
int bombLen = bomb.length();
for (char c : input.toCharArray()) {
sb.append(c);
if (sb.length() >= bombLen) {
int inputLen = sb.length();
if (sb.substring(inputLen - bombLen, inputLen).equals(bomb))
sb.delete(inputLen - bombLen, inputLen);
}
}
return sb.length() == 0 ? "FRULA" : sb.toString();
}
}복잡도
- 시간 복잡도: 각 문자마다 폭발 문자열 길이만큼 접미사를 비교하므로 문자열 길이를 , 폭발 문자열 길이를 이라 할 때 이다.
- 공간 복잡도: 결과 버퍼에 최대 개의 문자가 들어가므로 이다.
마무리
폭발 문자열 문제는 매번 전체를 다시 찾지 않는 순간 쉬워진다. 새로 붙은 문자 때문에 생긴 접미사만 확인하면 된다.
