1.문제

2.코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String str = br.readLine();
        String comp = br.readLine();
        int N = comp.length();
        //누적할 스택 ;
        Stack<Character> stack = new Stack<Character>();
        int cnt = 0;
        
        for(int i=0; i<str.length(); i++) {
        	stack.push(str.charAt(i));
        	if(stack.peek().compareTo(comp.charAt(cnt))==0) {
        		cnt++;
        		if(cnt==N) {
        			while(cnt-->0) {
        				stack.pop();
        			}
        			cnt=0;
        			
        			boolean check = true;
        			
    			out : while(check) {
	        			int start = (stack.size()-N-1>=0)?stack.size()-N-1:0;
	        			int end = stack.size();
	        			
	        			for(int j=start; j<end; j++) {
	        				if(stack.get(j).compareTo(comp.charAt(cnt))==0) {
	        					cnt++;
	        					if(cnt==N) {
	        						while(cnt-->0) {
	        							stack.pop();
	        						}
	        						cnt=0;
	        						continue out;
	        					}
	        				}else {
	        					cnt=0;
	        	        		if(stack.get(j).compareTo(comp.charAt(cnt))==0) 
	        	        			cnt++;
	        				}
	        			}
	        			check = false;
        			}
        			
        		}
        		
        	}else {
        		cnt = 0;
        		if(stack.peek().compareTo(comp.charAt(cnt))==0) {
        			cnt++;
        		}
        	}
        }
        
        
        StringBuilder sb = new StringBuilder();
        
        if(stack.isEmpty()) {
        	bw.write("FRULA");
        }else {
        	for(char c : stack) {
        		sb.append(c);
        	}
        	bw.write(sb.toString());
        }
        
        bw.flush();
        br.close();
        bw.close();
    }
}

3.Review

스택을 이용하여 풀었다.

원래는 StringBuilder에 문자열을 집어넣고 검사를 했었는데,시간초과가 나왔다.

스택을 이용하게 되면 O(N)으로 줄어들게 된다.