[BOJ] 9935 문자열폭발 (java)

민지·2024년 7월 27일

Algorithm-Solution

목록 보기

9/12

문제

접근 방향

String 문제여서 substring 메서드를 잘 쓰면 O(n)으로 통과할 수 있다고 생각함.
폭발 문자열 길이를 저장해놓고 이를 통해 인덱스를 제어하려고 했다.

첫번째 시도: 메모리 초과

사실 이게 3번째 시도인데, 1-2번째는 인덱스를 잘못 잡아서 인덱스 초과 런타임 에러 남.

아무튼 다 고치고 돌렸는데, 메모리 초과가 났다.

코드

package solution;

import java.io.*;

public class BOJ9935_문자열폭발 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String bomb = br.readLine();
        int len = bomb.length();
        for (int i = 0; i <= str.length() - len; ) {
            String tmp = str.substring(i, i + len);
            if(tmp.equals(bomb)) {
                // 같은 애들 삭제해준다,
                str = str.replace(tmp, "");
                // 인덱스를 현재 - len 으로 돌려서 다시 폭발 문자열이 생겼는지 체크
                i = i - len < 0 ? 0 : i - len ;
            } else {
                // 같지 않다면 다음 문자 탐색한다
                i++;
            }
        }
        System.out.println(str.length() == 0 ? "FRULA" : str);
    }
}

결과

44% 에서 메모리초과 났다.

str = str.replace(tmp, "")
이 부분에서 str이 String 불변객체이기 때문에 계속 새로 메모리를 차지해서 날 수 있겠다.

두번째 시도

그럼 메모리를 새로 저장하지 않는 StringBuilder 를 써봤다.

코드

        StringBuilder str = new StringBuilder(br.readLine());
        String bomb = br.readLine();
        int len = bomb.length();
        for (int i = 0; i <= str.length() - len; ) {
            String tmp = str.substring(i, i + len);
            if(tmp.equals(bomb)) {
                str.delete(i, i+len);
                i = i - len < 0 ? 0 : i - len ;
            } else {
                i++;
            }
        }

결과

ㅋㅋ 46%에서 시간초과 났다.

하암.. 문자열 메서드가지고 하면 안되는 문제같다.

세번째 시도: 스택

도저히 모르겠어서 분류를 봤는데 스택이 있는거다.
엥 ?? 이게 어떻게 스택을 쓸 수 있지 생각해봤다.

문자열의 앞부터 한칸한칸 따지면서 푸는 문제는 스택을 떠올리라고 오답노트에 적어논 적 있다.
가장 마지막을 탐색하는 문제인가 이게 ..?

다른 사람의 풀이를 보았다.

1. 스택에 문자열 앞부터 넣는다.

2. 스택 크기가 bombSize보다 크거나 같으면 스택을 탐색한다.

stack.get(int idx) 를 통해서 bomb 길이만큼 비교하고, 맞으면 pop() 하고 아니면 넘어간다.

여기서 bombSize가 max 36이기 때문에 10^6 * 36 으로 O(n)이 가능하다.

bombSize 만큼만 확인해도 되는 이유

한번 처리를 진행한 스택 안에는 폭발 문자열이 존재하지 않는다.
처리 전에 문자열이 하나 push 되고 비교하는 순간 사라지기 때문이다.
그래서 스택의 맨 상단만 체크해주면 된다.

코드

package solution;

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

public class BOJ9935_문자열폭발 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String bomb = br.readLine();
        int len = bomb.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            // 스택에 현재 문자를 넣는다.
            stack.push(str.charAt(i));
			// 스택 사이즈가 폭발 문자열보다 커지면, 가장 상단의 len만큼의 문자열을 비교하고 처리한다.
            if(stack.size() >= len) {
                boolean flag = true;
                for (int j = 0; j < len; j++) {
                    if(stack.get(stack.size() - len + j) != bomb.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {
                    for (int j = 0; j < len; j++) {
                        stack.pop();
                    }
                }
            }
        }
        StringBuilder ans = new StringBuilder();
        for(Character c : stack) {
            ans.append(c);
        }
        System.out.println(ans.length() == 0 ? "FRULA" : ans);
    }
}