백준 - 문자열 폭발
구해야 하는 것
- 주어진 문자열에서 폭발 문자열을 전부 제거하라
주어진 자료
- 문자열이 폭발 문자열을 포함하고 있으면 모든 폭발 문자열이 폭발. 남은 문자열을 순서대로 이어 붙여 새로운 문자열 만듦
- 새로 생긴 문자열에 폭발 문자열 포함 가능
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속됨
조건
- 1 <= 문자열 길이 <= 1,000,000
- 1 <= 폭발 문자열 길이 <= 36
- 모든 폭발이 끝난 후 남아있는 문자가 없으면 "FRULA" 출력
계획 1
- 문자열에 폭발 문자열이 포함되어 있으면 모두 없앤다.
- 폭발 문자열이 더이상 존재하지 않을 때까지 계속 없앤다.
- 폭발 문자열 제거가 끝났을 때 문자열 길이가 0이면 FRULA를 출력한다.
- 그렇지 않으면 문자열을 출력한다.
실행 1 → 메모리 초과
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String explodeStr = br.readLine();
boolean hasExplodeStr = true;
while(hasExplodeStr) {
hasExplodeStr = input.contains(explodeStr);
if(hasExplodeStr) { // 폭발 문자열이 포함 되어 있으면 모두 제거
input = input.replaceAll(explodeStr, "");
}
}
if(input.length() == 0) {
System.out.println("FRULA");
} else {
System.out.println(input);
}
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
계획 2
- 입력받은 문자열을 맨 뒤부터 스택에 쌓는다.
- 하나씩 꺼내보면서 폭발 문자열의 첫 번째 문자와 일치하면, 그때부터 폭발 문자열 길이만큼 돌면서 폭발 문자열과 계속 일치하는지 확인한다. 그리고 tmp에 저장해놓는다. 중간에 일치하지 않으면 isExplodeStr를 false로 바꾼 후 반복문 탈출한다.
- isExplodeStr가 false면 tmp를 newStr에 붙인다.
- 그렇게 만든 새로운 문자열이 폭발 문자열 제거 전의 문자열(input)과 같으면 더이상 폭발 문자열이 없는 것이므로 input을 출력한다.
- input의 길이가 0이면 "FRULA"를 출력한다.
실행 2 → 여전히 메모리 초과
public class Main {
// 입력 받은 문자열을 맨 뒤부터 스택에 쌓기
public Stack<Character> addStack(String input) {
Stack<Character> stack = new Stack<>();
for (int i = input.length() - 1; i >= 0; i--) {
stack.push(input.charAt(i));
}
return stack;
}
// 새로운 문자열 만들기
public String makeNewStr(Stack<Character> stack, String explodeStr) {
String newStr = "";
while(!stack.isEmpty()) {
char cur = stack.pop();
if (cur != explodeStr.charAt(0)) { // 폭발 문자열이 아니면
newStr += cur; // 새로운 문자열에 더함
} else { // 폭발 문자열의 첫 번째 문자와 일치하면
String tmp = "";
tmp += cur;
Boolean isExplodeStr = true;
// 폭발 문자열 길이만큼 돌면서 일치하는지 확인
for (int i = 1; i < explodeStr.length(); i++) {
if (stack.peek() != explodeStr.charAt(i)) { // 돌다 보니 폭발 문자열이 아닌 경우
isExplodeStr = false;
break;
} else {
cur = stack.pop();
tmp += cur;
}
}
if (!isExplodeStr) { // 폭발 문자열이 아니었으면 tmp에 저장된 것을 newStr에 붙여줌
newStr += tmp;
}
}
}
return newStr;
}
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String explodeStr = br.readLine();
Boolean hasExplodeStr = true;
while(hasExplodeStr) {
// 입력받은 문자열을 맨 뒤부터 스택에 쌓음
Stack<Character> stack = new Stack<>();
stack = addStack(input);
// 폭발 문자열을 제거해서 새로운 문자열을 만듦
String newStr = makeNewStr(stack, explodeStr);
// 폭발 문자열 제거 전과 제거 후가 같으면 더이상 폭발 문자열이 없는 것이므로 결과 출력
if(input.equals(newStr)) {
hasExplodeStr = false;
} else {
input = newStr;
}
}
// 문자열의 길이가 0이 되면 "FRULA"를 출력
if(input.length() == 0) {
System.out.println("FRULA");
} else {
System.out.println(input);
}
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
계획 3
- 입력받은 문자열을 스택에 쌓는다.
- 쌓다가 스택 크기가 폭발 문자열 크기와 같아지면 폭발 문자열인지 검사한다.
- 폭발 문자열이면 폭발 문자열 길이만큼 pop() 한다.
- 문자열 길이만큼 다 돌았으면 스택에서 꺼내서 문자열을 만든다.
- 문자열 길이가 0이면 "FAULA" 출력하고, 그렇지 않으면 문자열을 출력한다.
실행 3
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String explodeStr = br.readLine();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < input.length(); i++) {
stack.push(input.charAt(i)); // 입력받은 문자열을 스택에 쌓다가
if(stack.size() >= explodeStr.length()) { // 스택 크기가 폭발 문자열 크기 이상이 되면 검사 시작
Boolean isExplodeStr = true;
for(int j = 0; j < explodeStr.length(); j++) {
char cur = stack.get(stack.size() - explodeStr.length() + j);
if(cur != explodeStr.charAt(j)) {
isExplodeStr = false;
break;
}
}
if(isExplodeStr) { // 폭발 문자열이면 그 길이만큼 pop()
for(int j = 0; j < explodeStr.length(); j++) {
stack.pop();
}
}
}
}
// 결과 출력
StringBuilder sb = new StringBuilder();
for(Character c : stack) {
sb.append(c);
}
if(sb.length() == 0) {
System.out.println("FRULA");
} else {
System.out.println(sb.toString());
}
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
반성
- 예제 입력에 대한 결과는 맞게 잘 나오는데, 메모리 초과 때문에 삽질을 좀 했다. 우선 처음에는 '그냥 스택 안 써도 폭발 문자열을
replaceAll()로 다 없애버리면 되는 간단한 문제 아닌가?' 라고 생각했었는데,replaceAll()은 내부적으로 많은 Garbage Collection 객체가 생성되어 메모리를 효율적으로 사용할 수 없으므로 스택으로 풀어야 한다는 것을 알게 됐다.
그래서 스택으로 바꿔서 풀었는데도 여전히 메모리 초과가 발생해서 좀 혼란스러웠다. 지금 보니까 스택을 사용하긴 했으나, 문자열을 '끝까지' 다 스택에 넣었다가 빼는 방식이기 때문에 메모리 초과가 난 것 같다.
결국 다른 사람의 풀이를 좀 참고해서 스택 관리하는 로직은 잘 짰는데, 이번에는 시간 초과가 났다. String 대신 StringBuilder를 쓰니까 통과 되었는데, 찾아보니까 속도 차이가 엄청 나더라.. 앞으로는 그냥 StringBuilder를 쓰도록 해야겠다.