자바(백준) 9935 문자열 폭발

오답 노트 & 새로 알게 된 점

문제를 풀 때, 시간 제한으로 Stack을 사용해야겠다라는 생각까지 들었다.

그러나 구현 부분에서 막혀 풀지 못했다.

 

처음엔 stack의 개수가 (bomb길이 - 1) 일 때

길이 만큼 pop + 이제 넣을 문자 와 bomb을 비교하였다.

 

그러나 위와 같이 풀게 된다면 stack Size가 bomb의 길이보다 커지게 될 때 비교할 수 없게 된다.

 

또한, Stack의 참조형을 String으로 하게 되면 메모리 초과가 난다.

그래서 Character로 바꾸었더니 AC를 받았다.

아마 문제의 메모리 제한이 타이트해서 String을 하게 되면 틀리는 것 같다.

 

stack은 index의 접근이 안되는 줄 알았다.

그러나 get이라는 메서드가 있었고 index를 통해 stack에 접근할 수 있다!

 

어떻게 get을 사용할 수 있을까?

java에서 Stack 클래스는 Vector클래스를 상속한다.

여기서 Vector클래스에는 get이라는 메서드가 존재하게 된다.

 

---

 

풀이

stack Size가 bomb의 길이보다 크거나 같아질 때 비교를 한다.

이 때 중요한 점은

stack.get(stack.size() - bomb.length() + j) != bomb.charAt(j)

부분이다.

 

stack.size() - bomb.length() + j 가 왜 있을까?

예제 2를 봤을 때,

stack에 1 1 2 a 가 있게 된다.

그러면 112a와 bomb을 비교한다. 같지 않으므로 다음 문자를 stack에 넣는다.

 

1 1 2 a b가 stack에 있다.

1 1 2 a는 우리가 비교했으므로 비교할 필요 없다.

그렇다면 1 2 a b를 비교해야하는데 index 접근을 어떻게 해야할까?

 

바로

stack.size() - bomb.length() + j

이다. 

 

그래서 문자를 하나하나 비교하여 같으면 길이만큼 pop을 하고,

같지 않으면 다음 문자를 넣으면 된다.

 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static String s = "";
    static String bomb = "";
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        Stack<Character> stack = new Stack<>();
 
        for (int i = 0; i < s.length(); i++) {
            stack.push(s.charAt(i));
 
            if (stack.size() >= bomb.length()) {
                boolean flag = true;
 
                for (int j = 0; j < bomb.length(); j++) {
                    if(stack.get(stack.size() - bomb.length() + j) !=
                    bomb.charAt(j)){
                        flag = false;
                        break;
                    }
                }
 
                if(flag){
                    for (int j = 0; j < bomb.length(); j++) {
                        stack.pop();
                    }
                }
            }
        }
 
 
        StringBuilder sb = new StringBuilder();
        if(stack.isEmpty()) System.out.println("FRULA");
        else{
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }
            System.out.println(sb.reverse());
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        s = br.readLine();
        bomb = br.readLine();
    }
}
 

 

---

Reference

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Vector.html

Vector (Java SE 11 & JDK 11 )