9935번 - 문자열 폭발

1️⃣ 스택

 

✏️ 풀이 과정

스택을 조금 특이한 방법으로 활용해야 합니다. 일반적으로는 DFS와 같이 내부에서 실행되는 함수의 순서가 가장 먼저가 되도록 작동시키는데 여기서는 그 기능에 더해서 stack.get기능을 이용해 배열과 같이 탐색하는 로직이 필요합니다.(실제로 배열을 통해 구현되기때문에 배열처럼 인덱스로 값을 가져올 수 있습니다.)

 

해결 원리는 문자열을 한 글자씩 스택에 넣다가 주어진 패턴 문자열보다 같거나 커질 때 글자를 스택에 넣을 때마다 최근 p(패턴의 길이)개에 대해 패턴과 일치하는 지 검사하는 것입니다. 만약 패턴과 같다면 stack.pop을 통해 p개만큼 원소를 없애고 다음 글자로 이동합니다.

 

이와 같은 방법을 통해 중간에 있는 패턴 문자열을 스택을 통해 중첩된 것까지 모두 제거하고 남은 문자열을 얻을 수 있습니다. 또한 삼항 연산자로 빈 문자열일 경우 FRULA를 출력하면 문제가 해결됩니다.

 

⏱ 시간 복잡도

문자열이 패턴 길이와 같아진 이후 남은 문자열의 길이만큼 패턴 대조를 반복하기 때문에 시간복잡도는 O(S * P) (S는 문자열의 길이, P는 패턴의 길이)가 됩니다. 1000000 * 36 이므로 제한 시간 내에 문제 해결이 가능합니다.

 

💻 코드

Java

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

public class Main {
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String str = br.readLine();
        String pat = br.readLine();
        int sLen = str.length();
        int pLen = pat.length();
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<sLen;i++) {
        	stack.push(str.charAt(i));
        	boolean found = true;
        	if(stack.size() >= pLen) {
        		for(int j=0;j<pLen;j++) {
        			if(stack.get(stack.size()-pLen+j) != pat.charAt(j)) {
        				found = false;
        				break;
        			}
        		}
        		if(found) {
        			for(int j=0;j<pLen;j++) {
        				stack.pop();
        			}
        		}
        	}
        }
        for(char c:stack) {
        	sb.append(c);
        }
        System.out.print(sb.toString().equals("") ? "FRULA" : sb);
        br.close();
    }
}