https://www.acmicpc.net/problem/9935
문제 요약
문자열과 폭발 문자열이 주어진다.
문자열이 폭발 문자열을 포함하면 모든 폭발 문자열 부분은 사라지고, 남은 문자열이 합쳐져 새로운 문자열이 만들어진다.
새로 생긴 문자열에도 폭발 문자열이 있다면 같은 과정을 반복한다.
모든 폭발이 끝난 후 남는 문자열을 구하여라. 만약 남은 문자가 없다면 "FRULA"를 출력한다.
이때 문자열은 모두 알파벳 소문자, 대문자, 숫자로만 구성되며, 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
문자열의 길이는 최대 100만이다.
폭발 문자열의 길이는 최대 36이다.
문제 접근
주어진 문자열을 훑으면서 폭발 문자열을 찾다가, 폭발 문자열을 발견하면 해당 부분을 삭제하고 얻은 새로운 문자열을 다시 훑으면 될 것 같다.
하지만 새로운 문자열을 어떻게 훑을 지가 문제다.
- 처음부터 다시 훑기 시작하면 시간복잡도가 이 되는데, 문자열의 길이가 최대 100만이므로 시간 내에 수행이 불가능하다.
- 폭발한 인덱스를 기준으로 다시 훑기 시작하기에는 폭발 이전 인덱스와 이후 인덱스로 새로운 폭발 문자열이 발생하는 경우를 처리하기가 어려울 것 같다.
그렇다면 스택을 이용해서 문자열을 삽입하다가, 폭발 문자열을 만나면 제거하고 다시 진행하면 앞선 문제를 해결할 수 있을 것 같다.
그런데 어떤 경우에 스택에 문자를 넣고, 어떤 경우에 스택의 값을 꺼내서 폭발 문자열인지 확인해야 할까?
여기서 사용할 수 있는 힌트는 폭발 문자열에 동일한 문자가 존재하지 않는다는 것이다.
폭발 문자열의 첫 글자를 만나면 스택에 문자를 넣기 시작하고, 폭발 문자열의 마지막 글자를 만나면 스택의 값을 꺼내서 폭발 문자열인지 확인하는 것이다.
값을 넣는 개수와 값을 꺼내는 개수는 당연히 폭발 문자열의 길이만큼 수행해야 할 것이다.
이러한 과정을 거쳐 남는 문자열이 정답이 된다.
풀이
기본적인 아이디어는 다음과 같다.
- 주어진 문자열을 훑으며 폭발 문자열의 첫 문자와 같은지 확인한다.
- 만약 첫 문자와 같다면 폭발 문자열의 길이만큼 스택에 넣는다. 그 과정에서 첫 문자를 다시 만난다면 폭발 문자열의 길이만큼 스택에 넣는 개수를 추가한다.
- 문자를 스택에 넣는 과정에서 폭발 문자열의 끝 문자를 만나면 폭발 문자열 길이만큼 문자를 꺼내서 폭발 문자열과 같은지 확인한다.
- 만약 폭발 문자열과 같다면 해당 내용을 제거하고, 다르다면 스택에 다시 넣는다.
- 스택에 넣는 과정이 끝났다면 스택에 남은 문자를 정답 문자열에 추가한다.
- 위의 경우에 해당하지 않는 경우에는 현재 문자를 정답 문자열에 추가한다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder answer = new StringBuilder();
// 입력 받기
String input = br.readLine();
String burst = br.readLine();
// 각 문자열의 길이 얻기
int inputLen = input.length();
int burstLen = burst.length();
// 스택 구현
ArrayDeque<Character> stack = new ArrayDeque<>();
// 스택에 넣을 문자 개수를 기록하는 변수
int pushNum = 0;
// 입력 문자열을 하나하나 확인한다.
for (int i = 0; i < inputLen; i++) {
// 만약 해당 문자가 폭발 문자열의 첫 글자라면 pushNum을 폭발 길이만큼 더함
if (input.charAt(i) == burst.charAt(0)) {
pushNum += burstLen;
}
// pushNum이 남아있다면 answer대신 stack에 넣는다.
if (pushNum > 0) {
stack.push(input.charAt(i));
pushNum--;
// 만약 해당 문자가 폭발 문자열의 마지막 글자라면 확인해봐야 한다.
if (input.charAt(i) == burst.charAt(burstLen-1)) {
// stack의 크기가 burstLen보다 같거나 큰지 확인한다.
if (stack.size() >= burstLen) {
// burstLen만큼 꺼내서 폭발 문자열인지 확인한다.
StringBuilder sbTest = new StringBuilder();
for (int j = 0; j < burstLen; j++) {
sbTest.append(stack.pop());
}
sbTest.reverse();
String test = sbTest.toString();
// 만약 폭발 문자열이 아니라면 다시 스택에 넣는다.
if (!test.equals(burst)) {
for (int j = 0; j < burstLen; j++) {
stack.push(test.charAt(j));
}
}
}
}
// pushNum이 0이 되었는데 stack에 문자가 남아있다면 answer에 추가한다.
if (pushNum == 0 && !stack.isEmpty()) {
StringBuilder sbAdded = new StringBuilder();
while (!stack.isEmpty()) {
sbAdded.append(stack.pop());
}
sbAdded.reverse();
answer.append(sbAdded);
}
}
// pushNum에 해당하지 않으면 현재 문자를 answer에 넣는다.
else {
answer.append(input.charAt(i));
}
}
// 다 돌았는데 stack에 남은 문자가 있다면 answer에 넣어준다.
if (!stack.isEmpty()) {
StringBuilder sbAdded = new StringBuilder();
while (!stack.isEmpty()) {
sbAdded.append(stack.pop());
}
sbAdded.reverse();
answer.append(sbAdded);
}
if (answer.length() == 0) {
System.out.println("FRULA");
}
else {
System.out.println(answer);
}
}
}회고
틀렸던 이유
문자열을 훑는 과정이 끝났을 때, 스택에 문자를 넣는 과정을 수행하고 있었을 수도 있다. 그 경우에는 스택에 문자가 남아있기 때문에 이를 정답 문자열에 추가해야 한다.
