[백준 9935번] 문자열 폭발

문제 링크: 9935번 제목

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

 

s = ABCABCDEDE, p = ABCDE인 경우를 생각해보자.

스택에

C, 2

B, 1

A, 0

를 push한 이후, 다시 A를 만나게 되면, 패턴과 일치하지 않는다.

다만 새로 만나게 된 문자가 A로서 패턴의 첫 번째와 일치하므로(그렇지 않다면 A -1을 넣었을 것) A, 0을 넣어준다. 이렇게 하면, E, 4가 스택에 push된다는 것은 곧 패턴과 일치하는 문자가 스택에 포함되어 있다는 것을 보장한다. 따라서 p의 길이만큼 스택을 pop한다.

pop한 이후에는, pi를 스택의 top의 idx 다음 것으로 해서 패턴이 계속해서 연속되는지 확인한다.

 

import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

class Element {
    char ch;
    int idx;

    public Element(char ch, int idx) {
        this.ch = ch;
        this.idx = idx;
    }
}

public class Main {
    static String s;
    static String p;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        s = sc.next();
        p = sc.next();

        Stack<Element> stack = new Stack<>();
        int pi = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == p.charAt(pi)) {
                stack.push(new Element(s.charAt(i), pi));
                if (pi == p.length() - 1) {
                    for (int j = 0; j < p.length(); j++) {
                        stack.pop();
                    }
                    if (stack.isEmpty()) pi = 0;
                    else pi = stack.peek().idx + 1;
                    continue;
                }
                pi++;
            } else {
                pi = 0;
                if (s.charAt(i) == p.charAt(pi)) {
                    stack.push(new Element(s.charAt(i), pi));
                    pi++;
                } else {
                    stack.push(new Element(s.charAt(i), -1));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop().ch);
        }

        if (sb.length() == 0) {
            System.out.println("FRULA");
        } else {
            System.out.print(sb.reverse());
        }
    }
}