[Java/백준/문자열, 스택] 9935 - 문자열 폭발

문제

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{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> stack = new Stack<Character>();
		String input = br.readLine();
		String bomb = br.readLine();
		
		for(int i=input.length()-1; i>-1; i--) {
			stack.push(input.charAt(i));
			
			if(stack.size()>=bomb.length() && stack.peek()==bomb.charAt(0)) {
				boolean isBomb = true;
				for(int j=1; j<bomb.length(); j++) {
					if(stack.get(stack.size()-j-1) != bomb.charAt(j)) {
						isBomb = false;
						break;
					}
				}
				
				if(isBomb) {
					for(int j=0; j<bomb.length(); j++)
						stack.pop();
				}
			}
		}
		
		int size = stack.size();
		StringBuffer sb = new StringBuffer();
		if(stack.isEmpty()) {
			System.out.println("FRULA");
		}else {
			for(int i=0; i<size; i++)
				sb.append(stack.pop());
		}
		System.out.println(sb);
	}	
}

 

1. 우선 입력받은 문자열(input)을 거꾸로 Stack에 넣어준다

2. Stack에 한 글자씩 넣어줄 때마다 top을 폭탄 문자열(bomb)의 첫글자와 비교한다.

   2-1. 첫글자가 같으면 그 다음 문자를 비교해서 bomb와 같은 글자인지 확인한다.

   2-2. 같은 글자가 아니면 isBomb는 false가 되고,

   2-3. bomb와 완벽하게 같다면(isBomb==true) bomb의 길이만큼 stack에서 pop을 시켜준다.

   → 이렇게 글자가 하나씩 들어올 때마다 check해주면 한꺼번에 넣고 확인하는 것보다 훨씬 효율적이다.

3. 폭탄을 전부 터뜨리고 출력