[백준] | JAVA, 자바 | 9935번 - 문자열 폭발

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

---

문제 풀이 :

1. 문자열 입력받기

2. 폭발 문자열 입력받기

2-1. 폭발 문자열 길이 저장

3. 메모리 절약을 위해 StringBuilder를 stack처럼 사용

3-1. 폭발 문자열 탐색 및 제거

4. 문자열 출력

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 문자열 입력받기
        String s = br.readLine();
        // 2. 폭발 문자열 입력받기
        String boom = br.readLine();
        // 2-1. 폭발 문자열 길이 저장
        int boomLength = boom.length();

        StringBuilder sb = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            // 3. 메모리 절약을 위해 StringBuilder를 stack처럼 사용
            sb.append(s.charAt(i));
            // 3-1. 만약 sb 사이즈가 폭발 문자열 길이보다 길다면 폭발 문자열 탐색
            if (sb.length() >= boomLength) {
                boolean catchBoom = true;
                for (int j = 0; j < boomLength; j++) {
                    // 3-2. 탐색 중 문자열에 폭발 문자열이 없다면 catchBoom을 false 하고 for문 종료
                    if (sb.charAt(sb.length() - boomLength + j) != boom.charAt(j)) {
                        catchBoom = false;
                        break;
                    }
                }

                // 3-3. 폭발 문자열을 찾았다면 문자열에서 폭발 문자열 제거
                if (catchBoom) {
                    sb.setLength(sb.length() - boomLength);
                }
            }
        }

        // 4. sb 비어있다면 주어진 문자열 출력
        if (sb.length() == 0) {
            System.out.println("FRULA");
        } else {
            // 4-1. 비어있지 않다면 sb 출력
            System.out.println(sb);
        }
    }
}

 

---

최초 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 문자열 입력받기
        String s = br.readLine();
        // 2. 폭발 문자열 입력받기
        String boom = br.readLine();
        // 2-1. 폭발 문자열 길이 저장
        int boomLength = boom.length();

        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            // 3. 스택에 문자열 저장
            stack.addLast(s.charAt(i));
            // 3-1. 만약 스택 사이즈가 폭발 문자열 길이보다 길다면 폭발 문자열 탐색
            if (stack.size() >= boomLength) {
                boolean catchBoom = true;
                Character[] arr = stack.toArray(new Character[0]);
                for (int j = 0; j < boomLength; j++) {
                    // 3-2. 탐색 중 문자열에 폭발 문자열이 없다면 catchBoom을 false 하고 for문 종료
                    if (arr[stack.size() - boomLength + j] != boom.charAt(j)) {
                        catchBoom = false;
                        break;
                    }
                }

                // 3-3. 폭발 문자열을 찾았다면 문자열에서 폭발 문자열 제거
                if (catchBoom) {
                    for (int j = 0; j < boomLength; j++) {
                        stack.pollLast();
                    }
                }
            }
        }

        // 4. 스택이 비어있다면 주어진 문자열 출력
        if (stack.isEmpty()) {
            System.out.println("FRULA");
        } else {
            // 4-1. 비어있지 않다면 스택에 남은 문자열을 출력
            StringBuilder sb = new StringBuilder();
            for (Character c : stack) {
                sb.append(c);
            }
            System.out.println(sb);
        }
    }
}

 

 예제 결과는 맞게 나왔지만 메모리 초과