🧩 문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
예제
입력
mirkovC4nizCC44
C4출력
mirkovniz🎯 풀이
| 메모리 | 시간 | 코드길이 |
|---|---|---|
| 88500 KB | 500 ms | 1331 B |
Point
Stack을 이용하여 폭발문자열과 비교하고 폭발문자열과 완벽하게 일치한다면pop시켜준다.
Stack 이용
Stack을 이용하여 입력 문자열을 하나씩 쌓으면 비교하면 메모리 초과와 시간 초과를 피할 수 있다.
//폭발 문자열과 문자가 다르다면 중단
if(stack.get(stack.size() - bomb.length() + j) != bomb.charAt(j)) {
isMatch = false;
break;
}if문의 조건은 Stack의 마지막 부분이 폭파문자열들과 같은지를 비교한다. 이 부분을 모두 통과한다면 폭파 문자열과 같다고 판단하고 폭파 문자열의 길이만큼 pop 시킨다.
pop시킨 후에 Stack에 남아있는 문자와 더 추가되는 문자가 합쳐져서 폭파 문자열이 만들어지는지도 판단할 수 있다.
⭐️ 전체 풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class BJ9935_문자열폭발 {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String bomb = br.readLine();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < input.length(); i++) {
stack.push(input.charAt(i));
//stack의 문자열 개수가 폭탄문자열의 길이 이상일때부터 체크
if(stack.size() >= bomb.length()) {
boolean isMatch = true;
for(int j = 0; j < bomb.length(); j++) {
//폭발 문자열과 문자가 다르다면 중단
if(stack.get(stack.size() - bomb.length() + j) != bomb.charAt(j)) {
isMatch = false;
break;
}
}
if(isMatch) {
for(int j = 0; j < bomb.length(); j++) {
stack.pop();
}
}
}
}
if(stack.size() == 0) {
System.out.println("FRULA");
} else {
for(Character c : stack) {
sb.append(c);
}
System.out.println(sb);
}
} //Main 끝
}
처음 시도했던 방법은
stack이 아닌List를 사용하여 더 이상 폭파할 문자열이 없을 때까지 반복문을 돌리는 것이었다. 시간초과가 발생하였는데, 폭파 후 다시 끝까지 탐색, 폭파 후 다시 끝까지 탐색 ... 이 계속 반복되었기 때문인 것 같다. 결국,Stack을 사용해야한다는 힌트를 얻어 다시 풀었다.Stack을 사용했을 경우 앞에서부터 끝까지 폭파 문자열과 비교해야하는 과정이 줄어들어 성공할 수 있었던 것 같다.
