BaekJoon 9935. 문자열 폭발 (Java) (골드4) (문자열 조회)

문제출처: https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

---

문제 이해

목표

문자열이 있고, 폭발 문자열이 있다. 문자열 안에 폭발 문자열이 있다면 없애고 이어붙인다.  만약 폭발 문자열을 다 터트리고 남아 있는 문자가 있다면 정답으로 출력하고, 없으면 "FRULA"를 출력한다.

 

풀이

 

실패한 풀이: StringBuilder에 문자열을 담고, 문자열을 탐색하는 인덱스를 가리키는 i를 설정한뒤 indexOf로 i이후의 폭발 문자열을 찾도록 하여 원탐으로 폭발 문자열을 제거할 수 있는 코드를 짰다고 생각했다.  

 

실패 이유:

원탐으로 탐색할 때 indexOf로 String을 찾는 것은 어느정도 성능 부하가 있는 것 같다. 

그리고 폭발물을 제거하고 난 뒤에 이어 붙였을 때 다시 폭발물 문자가 있는지 확인하기 위해서 i를 갱신 시켜줘야 하는데, 이 작업을 반복적으로 너무 많이하게 되면 원탐이 아닌 경우가 된다고 생각한다. 

 

성공한 풀이: 

 

문자열을 원탐으로 탐색 => stack에 담으면서 탐색한다. 

문자열의 탐색하는 문자가
 폭발물 문자의 끝 문자와 같다면
 -> 해당 문자를 기준으로 폭발물 문자 길이만큼 stack의 문자들을 확인한다. 
   - 확인한 문자들이 폭발문 문자와 일치하면, stack에서 폭발문 문자들을 pop해서 제거한다.
   - 확인한 문자들이 폭발문 문자와 일치하지 않으면 다시 탐색을 진행한다.

 폭발물 문자의 끝 문자와 같지 않다면 
 -> stack에 담고 다음 문자를 탐색

 

탐색이 끝나면 

stack에 있는 문자들을 꺼내어 답을 만들어준다. 이때 주의할 점이 있다 아래 코드에서 확인하자.

---

소스코드

 

실패한 소스코드

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));
        StringBuilder sb = new StringBuilder();

        sb.append(br.readLine());
        String explodingStr = br.readLine();
        int length = explodingStr.length();
        int i = 0;
        while(true){
            int findIndex = sb.indexOf(explodingStr, i);
            if (findIndex == -1) {
                break;
            }
            sb.replace(findIndex, findIndex + length, "");
            if(findIndex - length < 0){
                i = 0;
            } else{
                i = findIndex - length;
            }
        }
        String answer;
        if(sb.toString().equals("")){
            answer = "FRULA";
        } else{
            answer = sb.toString();
        }
        System.out.println(answer);
    }
}

 

성공한 소스코드

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

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

        char[] charArr = br.readLine().toCharArray();
        char[] explCharArr = br.readLine().toCharArray();
        int explLength = explCharArr.length;
        Stack<Character> stack = new Stack<>();
        outer:
        for (char c : charArr) {
            if (stack.size() >= explLength - 1&& c == explCharArr[explLength - 1]) { // 마지막 문자열이 같으면
                stack.push(c);
                int stackLength = stack.size();
                for (int i = explLength - 1, j = 1; i >= 0; i--, j++) { // 폭발 문자열만큼 검사
                    if (stack.get(stackLength - j) != explCharArr[i]) {
                        continue outer; // 폭발 문자열이 아니면 다시 탐색 시작
                    }
                }
                for (int i = 0; i < explLength; i++) {
                    stack.pop();
                }
            } else { // 마지막 문자가 아니면
                stack.push(c);
            }
        }
        String answer;
        if (stack.isEmpty()) {
            answer = "FRULA";
        } else {
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }
            answer = sb.reverse().toString();
        }
        System.out.println(answer);
    }
}

---

개선전략

• StringBuilder의 append()와 insert()의 차이 ??
  위 코드에서 알고리즘은 동일한데, 답을 도출할 때

          String answer;
          if (stack.isEmpty()) {
              answer = "FRULA";
          } else {
              StringBuilder sb = new StringBuilder();
              while (!stack.isEmpty()) {
                  sb.insert(0, stack.pop());
              }
              answer = sb.toString();
          }
          System.out.println(answer);​

  append 메소드 대신 insert 함수를 사용하여 StringBuilder 앞에다가 값을 넣어주고 reverse를 따로 하지 않는 코드를 짜면, 해당 문제는 무조건 시간초과가 발생한다. !! 
  정말 이 사소한 문제로 시간초과가 발생한 게 의아 했지만, insert 함수가 해당 인덱스에 값을 넣어주면서, 기존의 값들을 모두 땡겨준다고 생각을 하니 과부하가 걸릴 수도 있다고 생각했다. 
  다음부턴 StringBuilder를 사용할 떄 append 함수를 지향하고 거꾸로 값을 넣을 일 있으면 reverse()를 사용하는게 훨씬 좋구나를 깨달았다. !!
• charArray로 풀기 vs String으로 풀기
  근소한 차이지만 charArray로 만들어 놓고 탐색하는게 더 빠른 것 같다. charAt() 함수로 일일히 타입변환을 안시켜도 되기 때문인 것 같다.
  
  
• Stack으로 풀기 vs List로 풀기
  Stack으로 풀었을 경우에 단점
  -> 정답을 도출하는 과정에서 stack.get( )을 써서 만들거나 pop을 해서 만들고 reverse를 해야 되는데 둘다 시간이 소요됨