백준 9935 문자열 폭발 Java

스택을 활용해서 풀어야 하는 문자열 폭발 문제이다. 정답률은 19%로 낮은 편이다.

문자열 A, B를 입력받고 A에서 B를 없애고 새로 만들어진 문자에서도 B를 없애고

계속해서 B를 없애면 되는 간단한 문제이다.

 

하지만 N제한은 백만으로 문자열이 새로 생길 때마다 검사하는 방법인 O(N^2)의 방식으로 푼다면

반드시 시간 초과가 나오게 된다.

 

시간 초과를 피하기 위해 스택을 사용하면 되는 문제이다.

스택을 사용하게 되면 O(N)만에 구현할 수 있다.

하지만 스택을 사용하면 된다라는 것을 눈치채도 구현하기 쉽지 않은 문제이다..

 

문제를 푸는 법은

1.  임의의 클래스에 A문자열의 위치, B문자열의 위치를 표시할 int형 변수 두 개를 필드로 만들어서 스택을 생성한다.

2. B문자열의 길이만큼의 boolean형 배열을 생성한다.

 

만약 B문자열의 길이가 1이라면 그냥 for문을 통해 지워준다.

 

길이가 1이 아니라면 

FOR문을 통해 A문자열을 하나씩 돌면서

1. B문자열의 첫 번째 값과 일치하면 우선 스택에 A문자열의 위치와 B문자열의 위치인 0을 넣는다.

2. B문자열의 첫 번째 값과 일치하지 않으면 스택에 가장 마지막(peek()) 값의 B 위치 값+1과 일치하는지 확인한다.

3. 일치한다면 스택에 넣는다. 만약 일치한 B위치 값이 B문자열의 마지막 위치값이라면 스택에서 B문자열의 길이만큼

    pop하면서 boolean형 배열에 A위치 값을 boolean형 배열에 표시한다.

4. 2번에서 일치하지 않는다면 스택에 있는 내용을 전부 지운다. 어차피 연결되지 않기 때문

5. boolean형 배열에서 지워지지 않은 것들의 위치 값들을 A문자열에서 출력한다.

 

주의해야 할점은 A문자열의 길이가 최대 백만이기 때문에

출력할 때 System.out.print로 하면 시간 초과가 나오게 된다.

StringBuilder를 사용하면 된다.

 

import java.util.Scanner;
import java.util.Stack;
 
public class Q9935 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String a = scan.nextLine();
        String b = scan.nextLine();
        int n = a.length();
        int m = b.length();
        boolean [] erased = new boolean[n];
        if(m == 1) {
            for(int i=0; i<n; i++) {
                if(a.charAt(i) == b.charAt(0)) {
                    erased[i] = true;
                }
            }
        }else {
            Stack<Pair> s = new Stack<>();
            for(int i=0; i<n; i++) {
                if(a.charAt(i) == b.charAt(0)){
                    s.push(new Pair(i, 0));
                } else {
                    if(!s.isEmpty()) {
                        Pair p = s.peek();
                        if(a.charAt(i) == b.charAt(p.y+1)) {
                            s.push(new Pair(i, p.y+1));
                            if(p.y+1 == m-1) {
                                for(int j=0; j<m; j++) {
                                    erased[s.pop().x] = true;
                                }
                            }
                        } else {
                            while(!s.isEmpty()) {
                                s.pop();
                            }
                        }
                    }
                }
            }
        }
        boolean printed = false;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++) {
            if(erased[i]) continue;
            sb.append(a.charAt(i));
            printed = true;
        }
        if(!printed) {
            System.out.println("FRULA");
        } else {
            System.out.println(sb.toString());
        }
    }
}
class Pair{
    int x;
    int y;
    
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}