백준 / 9935번 / 문자열 폭발
[문제]
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
[입력]
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
[출력]
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
[예제 입력]
mirkovC4nizCC44
C4[예제 출력]
mirkovniz[예제 입력 2]
12ab112ab2ab
12ab[예제 출력 2]
FRULA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String word = br.readLine(); // 문자열
String bomb = br.readLine(); // 폭발 문자열
int bomblen = bomb.length(); // 폭발 문자열 길이
Stack<Character> stack = new Stack<>();
for(int i=0; i<word.length(); i++) {
char c = word.charAt(i);
stack.add(c);
// 폭발 문자열 길이와 같거나 넘은 경우
if(stack.size() >= bomblen) {
boolean flag = true;
// 폭발 문자열과 같은 지 검사
for(int j=0; j<bomblen; j++) {
char c1 = stack.get(stack.size() - bomblen + j);
char c2 = bomb.charAt(j);
if(c1 != c2) {
flag = false;
break;
}
}
// 폭발 문자열과 같은 경우 (단어 폭파시키기)
if(flag) {
for(int k=0; k<bomblen; k++) {
stack.pop();
}
}
}
}
if(stack.size() == 0) {
System.out.println("FRULA");
}
else {
StringBuilder sb = new StringBuilder();
for (Character c : stack) {
sb.append(c);
}
System.out.println(sb);
}
}
}문자열과 폭발 문자열이 주어지고, 폭발 문자열이 있으면 그 문자열을 없애고 남은 문자열에서 폭발 문자열이 없을 때 까지 반복하는 형식이다.
Stack을 이용해서 풀었는데, 모든 문자를 Stack에 넣은 후 검사하는 것이 아니라
한 글자씩 추출해서 Stack에 넣고 폭발 문자열의 길이(bomblen) 씩만 검사를 하는 형식으로 문제를 풀었다.
boolean 변수를 하나 두고, bomblen만큼 글자를 검사하면
폭발 문자열의 글자와 내 문자열이 일치하는지 알 수 있다.
일치하는 경우엔 또 for문을 돌며 폭발 문자열 길이만큼 stack.pop 을 통해 문자열을 없애주면 된다.
이 과정이 끝난 후, 스택에 남아있는 문자가 없다면 FRULA를 출력하고,
그렇지 않은 경우 (남아있는 문자가 있는 경우)엔 해당 문자열을 다 이어서 출력해주면 된다.
이 때, StringBuilder를 쓰지 않고 표준 출력을 쓰면 시간초과가 뜨기 때문에 StringBuilder를 써줬다.
다른 사람들 코드를 봤을 때, 애초에 Stack을 쓰지 않고 StringBuilder를 사용하기도 했다.