문제: 문자열 폭발

문제해결 아이디어는 Stack 사용과 폭발 문자열의 인덱스 저장입니다.

스택의 역할

  • 문제를 해결하기 위한 자료형은 스택입니다. 스택을 통해 전체 문자열을 한 번만 훑어서 해결하도록 합니다.
  • 스택의 역할은 Pair(char, int)을 저장하고 있으며 char는 폭발 문자열 안에 포함된 문자, int는 char 문자의 인덱스를 나타냅니다.
  • 예를 들어 전체 문자열이 12ab112ab2ab이고, 폭발 문자열이 12ab이면, 스택에서 폭발 문자열을 만날때 마다 아래와 같이 저장을 합니다.
// Pair(char, int)
// Pair(폭발 문자열 안에 포함된 문자, char 문자의 인덱스)
stack.add(new Pair('1', 0));
stack.add(new Pair('2', 1));
stack.add(new Pair('a', 2));
stack.add(new Pair('b', 3));

문제 해결 방법

설명의 편의를 위해서 전체 문자열을 totalString, 폭발 문자열을 bombString이라 하겠습니다.

  • 전체 문자열을 for문으로 한 번 돌면서 아래의 연산을 수행합니다.
    • 스택이 비어있다면
      • totalString[i]이 bombString[0]과 같다면 stack.add(new Pair(totalString[i], 0))을 해줍니다.
      • totalString[i]이 bombString[0]과 다르다면 stack.add(new Pair(totalString[i], -1))을 해줍니다.
    • 스택이 비어있지 않다면
      • 스택의 top(bombString[nowIdx]) 값을 보고 다음 폭발 문자열을 이어붙일 수 있는지 판단합니다.
      • totalString[i]이 bombString[nowIdx+1]과 같다면 stack.add(new Pair(totalString[i], nowIdx+1))을 해줍니다.
      • totalString[i]이 bombString[nowIdx+1]과 같지 않다면 폭발 문자열의 시작 문자와 같은지 판단해줍니다. (bombString[0])
      • totalString[i]이 bombString[0]과도 다르다면 stack.add(new Pair(totalString[i], -1))을 해줍니다.
  • 위에서 새 문자(totalString[i])를 넣는 과정이 끝나면 스택 내부에 폭발 문자열이 있는지 판단합니다.
    • 판단 방법은 스택 내 Pair의 int 값이 bombString.length() -1이면 현재 폭발 문자열이 스택에 전부 들어왔음을 알 수 있습니다.
    • 그러면 bombString 길이만큼 stack.pop()을 해주고 다시 새 문자(totalString[i])를 넣는 과정을 반복하면 됩니다.

코드

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


public class Main {

    static class Pair {
        char c;
        int idx;

        public Pair(char c, int idx) {
            this.c = c;
            this.idx = idx;
        }
    }

    public static int N;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        N = target.length();

        Stack<Pair> stk = new Stack<>();

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

            char c = str.charAt(i);

            if (stk.isEmpty()) {
                int targetIdx = 0;
                if (c == target.charAt(targetIdx)) {
                    stk.add(new Pair(c, targetIdx));
                } else {
                    stk.add(new Pair(c, -1));
                }

            } else {
                int nowIdx = stk.peek().idx;

                // c가 다음에 와야할 알파벳이랑 일치하면
                char nxt = target.charAt(nowIdx + 1);

                if (c == nxt) {
                    stk.add(new Pair(c, nowIdx + 1));
                } else if (c == target.charAt(0)) {
                    stk.add(new Pair(c, 0));
                } else {
                    stk.add(new Pair(c, -1));
                }
            }

            // 제거할 문자열 있나 확인
            if (!stk.isEmpty() && stk.peek().idx == N - 1) {
                for (int loop = 0; loop < N; ++loop) {
                    if (!stk.isEmpty()) stk.pop();
                }
            }
        }

        if (stk.size() == 0) {
            System.out.println("FRULA");
        } else {
            StringBuilder sb = new StringBuilder();
            while (!stk.isEmpty()) {
                char c = stk.pop().c;
                sb.append(c);
            }
            System.out.println(sb.reverse().toString());
        }
    }
}