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

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

문제 풀이

 

검사 대상 문자열 : S, 폭발 문자열 : C

 

1.  S의 문자열을 차례대로 순회하면서 Stack에 추가한다.

2. 만약 추가한 문자가 C의 마지막 문자열과 같다면 C의 길이만큼 스택을 역탐색해 폭발 문자열인지 검사한다.

- 폭발 문자열인 경우, 폭발 문자열의 길이만큼 pop한다. 다시 1번으로

- 아닌 경우 pass. 다시 1번으로

 

 

라이브러리에서 주어지는 Stack에는 배열처럼 순회하는 메서드가 없습니다.(List 타입으로 캐스팅한다면 쓸 수는 있으나 많이 느립니다.) 폭발 문자열인지 확인하려면 문자열을 인덱스에 따라 순회해야 하므로 ArrayList를 스택처럼 사용해줍시다.

 

 

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
문자열 폭발
https://www.acmicpc.net/problem/9935
 */
public class Main {
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader("testcase.txt");

		List<Character> entire = reader.readLineIntoCharList();
		List<Character> explode = reader.readLineIntoCharList();

		char last_explode = explode.get(explode.size()-1);

		List<Character> stack = new ArrayList<>();
		for (int i = 0; i < entire.size(); i++) {
			stack.add(entire.get(i));
			if(i >= explode.size()-1 && entire.get(i) == last_explode) {
				if(isExplodeString(stack, explode)) {
					for (int j = 0; j < explode.size(); j++) {
						stack.remove(stack.size()-1);
					}
				}
			}
		}
		if (stack.size() == 0) {
			System.out.println("FRULA"); return;
		}else {
			StringBuilder sb = new StringBuilder();
			for (char c : stack) {
				sb.append(c);
			}
			System.out.println(sb.toString());
		}
	}

	public static boolean isExplodeString(List<Character> stack, List<Character> explode) {
		for (int i = 0; i < explode.size(); i++) {
			if(explode.get(explode.size()-1-i) != stack.get(stack.size()-1-i)) return false;
		}
		return true;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}