[백준] 문자열 폭발 (java) Stack

2020-03-27

문자열 폭발 (백준> 문자열 & Stack_Queue)

문제 링크

문제설명

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력 1 복사

mirkovC4nizCC44
C4

예제 출력 1 복사

mirkovniz

예제 입력 2 복사

12ab112ab2ab
12ab

예제 출력 2 복사

FRULA


풀이

package String;

import java.io.*;
import java.util.*;


public class beak_문자열폭발 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		String pattern = br.readLine();
		
		Stack<Character> stk = new Stack<>();
		
		for(int i=s.length()-1; i>=0; i--) {
			
			stk.push(s.charAt(i));// 일단 넣고
			
			if(stk.peek() == pattern.charAt(0) &&stk.size() >= pattern.length()) {// 같은 경우에는
				boolean ck = false;

					for(int j=0; j<pattern.length(); j++) {
						if(pattern.charAt(j) != stk.get(stk.size()-1-j)) {
							ck = true;
							break;
						}
					}
					
					if(ck == false) { // 같다는거니까 패턴만큼 pop
						for(int j=0; j<pattern.length(); j++)
							stk.pop();
					}
				
			}
		}//for
	
		if(stk.size() ==0)
			System.out.println("FRULA");
		else {
			int size = stk.size();
			for(int i=0; i<size; i++)
				System.out.print(stk.pop());
		}
		
	}
}

후기 (40min)

사실 replace로 풀면 문제가 쉽게 풀리는데 시간초과가 계속 떠서 탈락…

문자를 뒤에서부터 스택에 넣고 푸쉬 팝하는 방식으로 풀면 쉽게 풀 수 있었다!!

이걸 어떻게 생각해 내는지… 우앙

  • 처음 푼 방법
 public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s = bf.readLine();
		String pattern = bf.readLine();
		
		while(true) {
			boolean ck = false;
			
			if(s.length() == 0){
				System.out.println("FRULA");
				break;
			}
			else {
				if(s.contains(pattern))
					s = s.replaceAll(pattern, ""); // 소름... 치환한거 다시 넣어줘야지
				else {
					System.out.println(s);
					break;
				}
			}
			
		}//while
	}