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

풀이 ① - StringBuilder

1. 아이디어

• 입력 문자열을 한 문자씩 차례로 StringBuilder에 담아가면서 확인
• 폭발 문자열과 동일한 문자열이 StringBuilder에 존재하면, 삭제

2. 자료구조

• StringBuilder: 입력 문자열을 한 문자씩 담아가면서 폭발 문자열인지 확인

3. 시간 복잡도

• 입력 문자열 최대 길이: 10^6 (100만)
  => O(n^2) 미만으로 풀어야 함
  => O(n log n), O(n) 까지 가능

오답 노트 - 시간 초과

• 입력 문자열을 StringBuilder에 담음
  StringBuilder input = new StringBuilder(br.readLine());
  
  
• 입력 문자열을 한 문자씩 차례로 확인
  1) 폭발 문자열과 동일한 문자열이 존재하면, 동일 문자열 시작 index 저장
  2) 폭발 문자열 제거 후, 저장한 시작 index 의 폭발 문자열 길이 이전부터 다시 확인 반복
  => 폭발 문자열을 제거한 후 다시 앞 index로 돌아가서 확인하여, O(n) 을 초과하게 됨
  
  
• 폭발 문자열 제거: input.delete(i, i + bomb.length());

코드

import java.io.*;

public class Main_StringBuilder {
	static String input;		// 입력 문자열
	static String bomb;		// 폭발 문자열
    	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);

		input = br.readLine();
		bomb = br.readLine();

		for (int i = 0; i < input.length(); i++) {
			sb.append(input.charAt(i));

			if (sb.length() >= bomb.length()) {
				boolean isSame = true;
				int idx = sb.length() - bomb.length();

				for (int j = idx; j < sb.length(); j++) {
					if (sb.charAt(j) != bomb.charAt(j - idx)) {
						isSame = false;
						break;
					}
				}

				if (isSame)
					sb.delete(idx, idx + bomb.length());
			}
		}

		if (sb.length() == 0)
			System.out.println("FRULA");
		else
			System.out.println(sb.toString());
	}
}

풀이 ② - Stack

1. 아이디어

• 입력 문자열을 한 문자씩 차례로 Stack에 담아가면서 확인
  => Stack의 size >= 폭발 문자열의 길이인 경우,
  Stack에서 폭발 문자열 길이만큼의 문자를 get하여 폭발 문자열과 비교

• 폭발 문자열과 동일한 문자열이 Stack에 존재하면, 삭제

2. 자료구조

• Stack<Character>: 입력 문자열을 한 문자씩 Stack에 담아가면서 폭발 문자열인지 확인

3. 시간 복잡도

• 입력 문자열 최대 길이: 10^6 (100만)
  => O(n^2) 미만으로 풀어야 함
  => O(n log n), O(n) 까지 가능

코드

import java.io.*;
import java.util.Stack;

public class Main_Stack {
	static String input;		// 입력 문자열
	static String bomb;		// 폭발 문자열
	static Stack<Character> stack = new Stack<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);

		input = br.readLine();
		bomb = br.readLine();

		for (int i = 0; i < input.length(); i++) {
			stack.push(input.charAt(i));

			if (stack.size() >= bomb.length()) {
				boolean isSame = true;
				int idx = stack.size() - bomb.length();

				for (int j = idx; j < stack.size(); j++) {
					if (stack.get(j) != bomb.charAt(j - idx)) {
						isSame = false;
						break;
					}
				}

				if (isSame) {
					for (int j = 0; j < bomb.length(); j++)
						stack.pop();
				}
			}
		}

		if (stack.isEmpty()) {
			System.out.println("FRULA");
			return;
		}

		StringBuilder sb = new StringBuilder();
		for (char ch : stack)
			sb.append(ch);
		System.out.println(sb.toString());
	}
}

문자열 처리 시, 성능 비교 StringBuilder vs Stack

• 문자열 처리 문제의 경우,
  일반적으로 Stack보다는 StringBuilder가 시간, 메모리적으로 더 효율적
  
  
• ※ 그렇다고 무조건 StringBuilder만 고집하라는 것은 아님