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

문제 접근

LCS 알고리즘과 비슷한 느낌으로 현재까지의 문자가 패턴문자열의 몇번째 인덱스까지 일치했는지를 기억하면 된다고 생각했다(이게 가능한 이유는 패턴 내에 동일 문자가 존재하지 않는다는 조건이 주어져서 가능한 것임. 만약 해당 조건이 없다면 패턴문자열이 제거되고 새롭게 연결되는 문자열들의 연결부분에서 기존에 저장했던 dp인덱스 정보가 바꿔야 할 수도 있음). 여기까지는 큰 어려움없이 다들 접근 가능할 것이다.
그런데, 나같은 경우는 StringBuilder를 써서 패턴 문자열과 일치하는걸 끝까지 찾으면 sb에서 i-패턴문자열길이 ~ i까지 모두 지우려고 했다. 여기서 삭제에 대한 시간복잡도(중간 문자를 삭제하면 그 이후 문자열이 앞으로 당겨지는 시간복잡도는 최대 O(N)이다) 를 고려하지 않았다... 결국 시간초과로 터지고 스택을 도입하니 해결되었다.

문제 풀이

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

class Main {
    static String origin;
    static String pattern;

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

        Stack<Node> stack = new Stack<>();
        int i = 0;
        int j = 0;
        while (i < origin.length()) {
            if (origin.charAt(i) == pattern.charAt(j)) {
                if (j == pattern.length() - 1) {
                    stack.add(new Node(origin.charAt(i), j));
                    for (int count = 0; count < pattern.length(); count++) {
                        stack.pop();
                    }
                    j = 0;
                    Node prevNode = null;
                    if (!stack.isEmpty()) {
                        prevNode = stack.peek();
                    }
                    if (prevNode != null && prevNode.accumIndex != -1) {
                        j = prevNode.accumIndex + 1;
                    }
                } else {
                    stack.add(new Node(origin.charAt(i), j));
                    j++;
                }
            } else if (origin.charAt(i) == pattern.charAt(0)) {
                if (pattern.length() == 1) {
                    j = 0;
                } else {
                    stack.add(new Node(origin.charAt(i), 0));
                    j = 1;
                }
            } else {
                stack.add(new Node(origin.charAt(i), -1));
                j = 0;
            }
            i++;
        }


        if (stack.isEmpty()) {
            System.out.println("FRULA");
        } else {
            StringBuilder sb = new StringBuilder();
            for (i = 0; i < stack.size(); i++) {
                sb.append(stack.get(i).c);
            }
            System.out.println(sb);
        }
    }
}

class Node {
    final char c;
    final int accumIndex;

    Node(char c, int accumIndex) {
        this.c = c;
        this.accumIndex = accumIndex;
    }
}

이 문제에서 스택의 Node에다가 지금까지의 일치 인덱스 번호를 저장시키므로 일종의 dp라고도 볼 수 있다.