[BOJ 9935] 문자열 폭발 (Java)

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

9935번: 문자열 폭발

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

public class Main_BOJ_9935 {

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String original=br.readLine();
		String explode=br.readLine();
		int len=explode.length();
		Stack<Character> stack=new Stack<>();
		for (int i=0; i<original.length(); i++) {
			stack.push(original.charAt(i));
			if (stack.peek()==explode.charAt(len-1) && stack.size()>=len) {
				int idx=len-1;
				Stack<Character> temp=new Stack<>();
				boolean isSame=true;
				while (idx>=0) {	//길이만큼 pop 하기
					char c=stack.pop();
					temp.push(c);
					if (c!=explode.charAt(idx)) {
						isSame=false;
						break;
					}
					idx--;
				}
				if (!isSame) {		//아니면 다시넣기 
					while (!temp.isEmpty()) {
						stack.push(temp.pop());
					}
				}
			}
		}
		if (stack.size()==0) {
			System.out.println("FRULA");
		}
		else {
			char[] ans=new char[stack.size()];
			int i=stack.size()-1;
			while (!stack.isEmpty()) {
				ans[i--]=stack.pop();
			}
			System.out.println(new String(ans));
		}
		
	}

}

처음엔 단순하게 풀었다가 결과는 메모리 초과 ..

stack이라는 힌트를 이용해서 풀었다.

 

stack에 순차적으로 문자열의 문자를 넣어주다가, 폭발 문자열의 마지막 문자를 만나면 그때부터 폭발 문자열의 길이 len 개만큼 stack 에서 pop해서 비교한다, 만약 다른 문자가 나왔을 경우를 대비해 temp 스택을 만들어 pop한 문자를 임시 저장한다.

다른 문자가 나왔을 경우, flag 값을 false 로 설정하여 temp 스택에 있는 값을 다시 원래 스택에 넣어줘서 원상복구 시킨다. 

 

다른 분(https://simsimjae.tistory.com/40) 의 코드를 보니, 더 간단하게 풀 수 있다.

result 배열에 차례대로 문자열의 문자를 넣어주다가, 폭발 문자열의 마지막 문자열을 만나면 그 길이만큼 비교한 후,

만약 다른 문자가 나왔을 경우 flag에 false를 준다.

flag가 true면, 즉 폭발 문자열과 같은 부분 문자열이 발견되었을 경우 result 배열의 index를 폭발 문자열 길이만큼 빼줘서 덮어쓰기가 되도록 함으로써, 자연스럽게 삭제되는 효과를 준다. 다른 문자열이 발견되었을 경우 별다른 처리를 해주지 않는다.