문제
이해
입력으로 기본 문자열과 폭발 문자열이 주어진다.
폭발 문자열은 기본 문자열에 포함될 수 있으며 폭발할 수 있다.
폭발했을 때 폭발 문자열은 그 자리에서 사라지고 남은 문자열이 다시 합쳐진다.
합쳐지는 과정에서 다시 폭발 문자열이 포함되어 있을 수도 있다.
이러한 과정을 폭발 문자열이 없을 때까지 반복하여 최종 문자열을 출력한다.
남은 문자열이 없다면 FRULA를 출력한다.
접근
풀이1
처음에는 문자열 비교를 위해 0부터 탐색하여 첫 문자가 같으면 해당 문자가 폭발 문자열의 시작인지를 판단했다.
판단한 뒤에는 문자열을 substring을 활용해 자르고 다시 붙혔다.
한번 폭발하면 다시 붙힌 뒤 탐색하는 인덱스를 합친 지점부터 다시 시작하게 했다.
static String recursive(String s) {
StringBuilder sb = new StringBuilder();
if (s.equals("")) {
return "FRULA";
}
boolean flag = false;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == bomb.charAt(0)) {
if (bomb.equals(s.substring(i, i + bomb.length()))) {
s = s.substring(0, i) + s.substring(i + bomb.length());
i -= bomb.length();
if (i < 0) {
i = 0;
}
flag = true;
}
}
}
if (flag) {
return recursive(s);
} else {
return s;
}
}재귀적으로 설계했다. 첫번째 재귀에서는 문자열을 쭉 탐색하고 폭발 문자열을 찾고 폭발 시킨다. 이후 만들어진 새로운 문자열을 다시 재귀를 통해 검사하고 폭발하지 않을 때까지 재귀했다.
하지만 이 풀이는 메모리 초과가 발생했는데 아무래도 함수 호출이 너무 많아서 그런 것 같았다.
따라서, 다른 풀이로 시도했다.
풀이2
이번에는 스택을 활용해보았다.
기본적으로는 문자열을 읽으면서 스택에 차례로 넣는다.
만일 넣을 문자열이 폭발 문자열의 끝 문자와 같다면 이전에 스택에 넣었던 문자들을 차례로 빼내면서 폭발 문자열을 확인한다.
이로써, 다음 2가지 분기로 나뉜다.
-
폭발 문자열이 맞을때
이때는 그냥 빼낸 문자열 다음으로 다시 새로운 문자를 삽입하면 된다. -
검사 도중에 폭발 문자열이 아님을 확인했을 때
스택에서 빼낸 문자가 폭발 문자열의 문자가 아닌 경우 다시 넣어야 한다. 이를 위해서 검사를 위해 스택에서 문자를 빼낼 때 다른 스택에 삽입하였다. 맞는 경우에는 두번째 스택을 그냥 버리고 아닌 경우에는 두번째 스택을 다시 꺼내 첫번째 스택에 집어넣는다.
for (int i = 0; i < str.length(); i++) {
stk.add(str.charAt(i));
if (stk.peek() == bomb.charAt(bomb.length() - 1)) {
Stack<Character> stk2 = new Stack<>();
for (int j = 0; j < bomb.length(); j++) {
if (!stk.isEmpty() && stk.peek() == bomb.charAt(bomb.length() - 1 - j)) {
stk2.add(stk.pop());
continue;
} else {
while (!stk2.isEmpty()) {
stk.add(stk2.pop());
}
break;
}
}
}
}위와 같이 코드를 작성했고 예외처리나 인덱스만 잘 설정하면 된다.
코드
import java.util.*;
import java.io.*;
public class Main {
static String str;
static String bomb;
static Stack<Character> stk;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
stk = new Stack<>();
str = br.readLine();
bomb = br.readLine();
for (int i = 0; i < str.length(); i++) {
stk.add(str.charAt(i));
if (stk.peek() == bomb.charAt(bomb.length() - 1)) {
Stack<Character> stk2 = new Stack<>();
for (int j = 0; j < bomb.length(); j++) {
if (!stk.isEmpty() && stk.peek() == bomb.charAt(bomb.length() - 1 - j)) {
stk2.add(stk.pop());
continue;
} else {
while (!stk2.isEmpty()) {
stk.add(stk2.pop());
}
break;
}
}
}
}
for (int i = 0; i < stk.size(); i++) {
sb.append(stk.get(i));
}
if (sb.toString().equals("")) {
System.out.println("FRULA");
} else {
System.out.println(sb.toString());
}
}
}결과
