백준 9935번 : 문자열 폭발 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

문자열 폭 골드 4

 

📖 문제

 

문제에 나온대로 반복해서 삭제 시도 --- 메모리, 시간 초과

Stack으로 풀어보면 되지 않을까 싶어서 Stack으로 풀었다. 

 

그리고 바로 더 좋은 방법이 있나 생각해봤는데 

StringBuilder에 문자 하나씩 넣고 폭발 문자 끝단어와 현재 탐색하는 단어가 같으면 

폭발 문자가 있을 가능성이 있으므로

 

StringBuilder.length - 폭발문자 길이 부터 끝까지를 추출해서 폭발 문자와 같은 지 확인하고 맞다면 삭제하는 식으로 하면된다.

 

 

---

🔅 1차 Stack 문제 풀이 (600ms)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        String str = br.readLine();
        String boomStr = br.readLine();
        Stack<Character> stack = new Stack<>();

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

            if(stack.size() >= boomStr.length()
                    && str.charAt(i) == boomStr.charAt(boomStr.length() - 1)) {
                int tmp = boomStr.length();
                while (tmp-->0) {
                    sb.append(stack.pop());
                }

                // 폭발 문자열이 아니면 다시 스택에 넣음
                if (!sb.reverse().toString().equals(boomStr)) {
                    for (int j = 0; j < sb.length(); j++) {
                        stack.push(sb.charAt(j));
                    }
                }

                sb.delete(0, sb.length());
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        bw.write(sb.length() == 0 ? "FRULA" : sb.reverse().toString());
        bw.flush();
        bw.close();
    }

}

 

🔅 2차 StringBuilder 문제 풀이 (300ms)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        String str = br.readLine();
        String boomStr = br.readLine();

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

            if(sb.length() >= boomStr.length()
                    && str.charAt(i) == boomStr.charAt(boomStr.length() - 1)) {

                int range = sb.length() - boomStr.length();
                if (sb.substring(range).equals(boomStr)) {
                    sb.delete(range, sb.length());
                }
            }
        }


        bw.write(sb.length() == 0 ? "FRULA" : sb.toString());
        bw.flush();
        bw.close();
    }

}

 

❗ 오답노트 / 필요한 지식

1.  일단 문제를 어떻게든 풀고 다른 방법은 없는지 리팩토링할 수 있는지 고민하는 건 잘 하고 있는 것 같다.