[JAVA] BOJ(백준) - 문자열 폭발 - 9335

문제내용

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

---

문제풀이

처음에 문제를보고 뭐야 너무 쉬운거 아닌가? 생각했다. 이유는 String 메소드인 reqlaceAll() , contains 를 쓰면 쉽게 할수 있다고 생각했기 때문...

imort ...

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		String boom = br.readLine();
		
		while(true) {
			str = str.replaceAll(boom, "");
			if(!str.contains(boom)) break; 
		}
		if(str.length()==0) System.out.println("FRULA");
		else System.out.println(str);
	}
}

근데 이렇게 풀면 메모리초과가 난다. 아마 주어지는 문자열의 길이가 최대 100만 이기때문인듯?

 

그래서 다른 방법이 필요했고, 기본적인 생각은 주어진 문자열 str을 탐색하는것과 동시에 boom문자열이 나왔을때 지워가된다고 생각했다. 하지만 로직이 처음 접한 문제라 그런지 로직이 쉽게 떠오르지 않았고, 다른사람 풀이를 봤는데 매우간단한 로직이었다.

 

1. str 문자열 탐색 ㄱㄱ

2. 탐색하면서 별도의 저장공간에 탐색된 문자를 차례대로 넣어줌.

3. 저장공간의 길이가 boom,length() 이상이 되는 순간부터 문자하나 넣을때 마다 boom이 있는지 검사.

4. 있으면 지우고, 없으면 넘어감.

5. 모든 문자 탐색 후 출력

 

기본적으로 이렇게 1~4번을 반복해서 나온 문자열을 출력해주면 된다.

그리고 다른 사람들 풀이를 보면 스택을 사용해서 푼사람이 많은데 굳이 꼭 스택을 사용할 필요는 없다.

여기서 중요한 로직은 별도의 저장공간의 길이를 size 라고 할때,

size-boom.length()+인덱스  -> 라는게 제일 중요한 부분이다.

 

즉, boom.length() = 2 , size = 5라고 한다면

0

1

2

3

4

0

1

=

0

1

2

3

4

0,1,2번 인덱스는 제외하고 3번 인덱스부터 boom.length() 길이만큼 탐색하게된다.

 

코드를 보고 생각해 보자.

 

---

코드

 

ArrayList사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		String boom = br.readLine();
		
		List<Character> list = new ArrayList<Character>();
		for(int i=0; i<str.length(); i++) {
			list.add(str.charAt(i));
			
			if(list.size() >= boom.length()) {
				boolean flag = true;
				for(int j=0; j<boom.length(); j++) {
					if(list.get(list.size()-boom.length()+j)!=boom.charAt(j)) {
						flag = false;
						break;
					}
				}
				if(flag) {
					for(int j=0; j<boom.length(); j++) 
						list.remove(list.size()-1);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<list.size(); i++) 
			sb.append(list.get(i));
		
		if(sb.toString().length()==0) System.out.println("FRULA");
		else System.out.println(sb.toString());
	}
}

---

StringBuilder 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		String boom = br.readLine();
		
		StringBuilder sb = new StringBuilder(str);
		StringBuilder ans = new StringBuilder();
		for(int i=0; i<sb.length(); i++) {
			ans.append(sb.charAt(i));
			
			if(ans.length() >= boom.length()) {
				boolean flag = true;
				for(int j=0; j<boom.length(); j++) {
					if(ans.charAt(ans.length()-boom.length()+j)!=boom.charAt(j)) {
						flag = false;
						break;
					}
				}
				if(flag) ans.delete(ans.length()-boom.length(),ans.length());
			}
		}
		
		if(ans.toString().length()==0) System.out.println("FRULA");
		else System.out.println(ans.toString());
	}
}

---

마치며

이번 문자열 문제는 처음 접해보는 문제였는데 나름 재밌었던 문제다. 특히, 인덱스를 재정의 하는부분을 새롭게(?) 알아가서 개인적으론 좋은 문제였다고 생각한다.