[백준] no9935: 문자열폭발 - Stack

문제

탐색할 대상 문자열과 필터링 해야할 문자열이 주어진다.

탐색 대상 문자열에서 필터링 해야할 문자열을 모두 제거 후 남은 문자열을 출력하기.

단, 남은 문자열이 빈 문자열일 경우 FRULA출력

---

원리

Stack을 이용한 탐색 (또는 StringBuilder를 이용)

* 단, 두 개 이상의 자료구조(Stack 등)를 사용할 시, 메모리 초과 발생

---

나의 코드

[메모리 초과] Stack방식으로 순차적인 탐색을 진행하여, 필터링 해야할 문자열을 모두 제거

1.  원리

1. Deque를 사용해 두 개의 Stack을 만들어 준다.
2. 첫 번째 Stack(dq)에는 탐색 대상 문자열의 문자를 순차적으록 담아준다.
3. 만약, 탐색 중 필터링해야할 문자열(boom)의 마지막 문자와 같은 문자가 들어온다면, 
   첫 번째 Stack의 끝에서부터 하나씩 꺼내서 비교해본다.
4. 이 과정에서 일차하는 문자라면 두 번째 Stack(clipBoard)에 차례로 담는다.
5. 만약 끝까지 일치한다면, 클립보드에 담긴 문자들을 모두 지우고 다음순서 탐샛을 진행한다.
6. 만약 중간에 일치하지 않는다면, 비교하던것들 원상복귀 시키고 이어서 탐색.

2. 문제

메모리초과 : 두 개의 스택을 사용함으로써 발생하는 부하 증가

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;

public class no9935 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static Deque<Character> dq, clipBoard;
    private static String str, boom;

    public static void main(String[] args) throws IOException {
        // 탐색할 문자열
        str = br.readLine();
        // 필터링 할 단어
        boom = br.readLine();
        // 남는 단어 넣을 기본 배열
        dq = new ArrayDeque<>();
        /* 비교군 비울 배열
        1. 필터링 할 단어의 역순으로 순차적으로 비교해서 일치하면 담음
        2. 만약 모두 일치하면 비우기
        3. 만약 중간에 일치하지 않으면 다시 원위치 시킴
        */
        clipBoard = new ArrayDeque<>();
        char last = boom.charAt(boom.length() - 1);

        // 비교용 문자열이 1자리일 경우, 그것만 다 지워줌
        if(boom.length()==1) {
            str = str.replaceAll(boom, "");
            System.out.println(str);
        }
        else {
            int now = 0;
            while (now < str.length()) {
                // dq에 남은 문자가 비교용 단어의 길이보다 짧을 때, 최소한의 비교할 만큼의 문자를 채워줌
                if (dq.size() < boom.length() - 1) {
                    while (dq.size() != boom.length()-1) {
                        dq.add(str.charAt(now));
                        now++;
                    }
                    continue;
                }

                char nowChar = str.charAt(now);
                now++;

                // 마지막 문자와 같은 것이 걸렸을 때,
                if (nowChar == last) {
                    clipBoard.push(nowChar);
                    for (int j = boom.length() - 2; j >= 0; j--) {
                        // 비교해서 일치하면 클립보드에 넣어줌
                        if (dq.peekLast() == boom.charAt(j)) {
                            clipBoard.addLast(dq.pollLast());
                            if(j==0) clipBoard = new ArrayDeque<>();
                        }
                        // 비교해서 일치하지 않으면, 클립보드에 있는애들 다 원상복귀 후, nowChar도 넣어줌
                        else {
                            while(!clipBoard.isEmpty()) dq.addLast(clipBoard.pollLast());
                            break;
                        }
                    }
                }
                else {
                    dq.add(nowChar);
                }
            }
            String result = "";
            int size = dq.size();
            for(int i=0 ; i<size ; i++) {
                result += dq.poll();
            }

            if(result.equals("")) System.out.println("FRULA");
            else System.out.println(result);
        }
    }
}

 

[성공] 레퍼런스를 참고하여 작성한 방식

: 필터링 할 문자열의 크기 이상일 경우, 탐색하여 일치하는 구간을 제거하는 방식

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static Stack<Character> dq;
    private static String str, boom;

    public static void main(String[] args) throws IOException {
        // 탐색할 문자열
        str = br.readLine();
        // 필터링 할 단어
        boom = br.readLine();
        int size = boom.length();
        // 남는 단어 넣을 기본 배열
        dq = new Stack<>();
        /* 비교군 비울 배열
        1. 필터링 할 단어의 역순으로 순차적으로 비교해서 일치하면 담음
        2. 만약 모두 일치하면 비우기
        3. 만약 중간에 일치하지 않으면 다시 원위치 시킴
        */


        // 비교용 문자열이 1자리일 경우, 그것만 다 지워주고 출력 (끝)
        if(boom.length()==1) {
            str = str.replaceAll(boom, "");
            System.out.println(str);
        }
        // 그 외의 경우
        else {
            for(int i=0; i<str.length(); i++) {
                dq.push(str.charAt(i));

                // 폭발 문자열과 길이가 같아지면 탐색 시작
                if(dq.size()>= size) {
                    boolean flag = true;

                    // st.size-regexSize부터 ~ st.size까지 탐색하여 regex와 일치하면 제거
                    for(int j=0; j<size; j++) {
                        if(dq.get(dq.size()-size+j) != boom.charAt(j)) {
                            flag = false;
                            break;
                        }
                    }
                    if(flag) {
                        for(int j=0; j<size; j++) {
                            dq.pop();
                        }
                    }
                }

            }

            StringBuilder sb = new StringBuilder();
            for(Character c : dq) {
                sb.append(c);
            }
            System.out.println(sb.length()==0? "FRULA" : sb.toString());
        }
    }
}

---

레퍼런스

참고링크 : https://code-lab1.tistory.com/80#google_vignette