백준 문자열 폭발(9935번)

이 문제는 replace를 사용하면 메모리가 초과 된다.

따라서 stack을 이용하여 풀어야 정답이 나오게 된다.

 

또한 scanner를 통해 입력받고 출력 시킨 결과 시간 초과가 나왔고

따라서 bufferreader를 사용하게 되었다.

 

알고리즘은 입력받은 문자열을 스택에다 넣어주면서

삭제할 문자열과 스택 사이즈가 같아질때 부터 스택을 검사하기 시작하고

카운트를 통해 검사하여 삭제할 문자열과 카운트의 수가 동일 할시에 

삭제할 문자열의 길이만큼 스택에서 삭제시키고 다음 문자열을 받는 알고리즘 이다. 

 

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));
		String str = br.readLine();
		String del = br.readLine();
		Stack<Character> s = new Stack<Character>();
		int count=0;
		
		for(int i =0; i<str.length(); i++) {	// 문자열 길이만큼 반복
			s.push(str.charAt(i));	//문자 하나씩 스택에 넣기
			if(s.size()>=del.length()) {	// 스택의 사이즈가 삭제시킬 문자열 보다 크지 않다면 할 필요 없음
				for(int j=0; j<del.length(); j++) {	//삭제할 문자열 길이만큼 실행
					if(s.get(s.size()-del.length()+j) == del.charAt(j)) {	// 스택의 문자가 삭제할 문자와 같다면 실행
						count++;	// 카운트 증가
					}else {	// 삭제할 문자가 아니라면
						break;	// 반복 종료
					}
				}
				if(count == del.length()) {	//카운트가 삭제할 문자열 길이와 같을시
					for(int j=0; j<del.length(); j++) {	// 삭제할 문자열 길이만큼 반복 
						s.pop();	// 스택에서 빼기
					}
					count = 0;	//카운트 초기화
				}else {	// 카운트가 삭제할 문자열 길이와 다르다면
					count = 0;	// 카운트 초기화
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(Character c : s) {
			sb.append(c);
		}
		System.out.println(sb.length()==0? "FRULA" : sb.toString());	//길이가 0이면 FRULA 아니면 문자열 출력
	}
}