알고리즘/PS
[백준 9935번][Java] 문자열 폭발 - 스택
johnna_endure
2020. 9. 26. 15:47
9935번: 문자열 폭발
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모�
www.acmicpc.net
문제 풀이
검사 대상 문자열 : 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());
}
}