[JAVA] 백준 9935. 문자열 폭발 :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 문자열을 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

사진을 클릭하면 문제 페이지로 이동합니다

 

2. 입출력 예제

 

3. 접근

1. 원본 문자열의 길이 N(1이상 1백만 이하), 비교 문자열의 길이 M(1이상 36이하) 일 때, 원본 문자열을 한 번 순회하면서 비교 문자열을 지우는 작업은 O(NM)의 시간 복잡도를 가진다.

2. O(NM)의 복잡도가 수없이 반복되기 때문에 제한시간을 맞출 수 없다. 따라서 문자열을 순회하면서 비교 문자열과 비교하는 작업을 병행한다.

3. 원본 문자열을 저장할 자료구조는 StringBuilder나 Stack 그 외 List와 같은 mutable 구조를 사용하면 된다.
   

4. 어떤 자료구조를 사용하든 간에 남은 원본 문자열을 출력해야 하므로 StringBuilder가 다른 자료구조에 비해 빠르다.

 

4. 코드

4-1. Stack 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main {
    static String origin;
    static String bomb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        origin = br.readLine();
        bomb = br.readLine();
        
        int oriLen = origin.length();
        int bombLen = bomb.length();
        Stack<Character> st = new Stack<>();
        
        for(int i = 0; i < oriLen; i++) {
            char c = origin.charAt(i);
            st.add(c);
            if(st.size() >= bombLen) {
                // 폭발 문자열과 서브 문자열이 같은지 검사
                boolean isSame = true;
                for(int idx = 0; idx < bombLen; idx++) {
                    char c1 = st.get(st.size() - bombLen + idx);
                    char c2 = bomb.charAt(idx);
                    if(c1 != c2) {
                        isSame = false;
                        break;
                    }
                }
                if(isSame) {
                    for(int cnt = 0; cnt < bombLen; cnt++) {                        
                        st.pop();
                    }
                }
            }
        }
        if(st.size() == 0) {
            System.out.println("FRULA");
        } else {
            StringBuilder sb = new StringBuilder();
            for(char c : st) {
                sb.append(c);
            }
            System.out.println(sb.toString());
        }
    }
}
 

 

4-2. StringBuilder 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main {
    static String origin;
    static String bomb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        origin = br.readLine();
        bomb = br.readLine();
        
        int oriLen = origin.length();
        int bombLen = bomb.length();
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < oriLen; i++) {
            char c = origin.charAt(i);
            sb.append(c);
            if(sb.length() >= bombLen) {
                // 폭발 문자열과 서브 문자열이 같은지 검사
                boolean isSame = true;
                for(int idx = 0; idx < bombLen; idx++) {
                    char c1 = sb.charAt(sb.length() - bombLen + idx);
                    char c2 = bomb.charAt(idx);
                    if(c1 != c2) {
                        isSame = false;
                        break;
                    }
                }
                if(isSame) {
                    sb.delete(sb.length() - bomb.length(), sb.length());
                }
            }
        }
        if(sb.length() == 0) {
            System.out.println("FRULA");
        } else {
            System.out.println(sb.toString());
        }
    }
}
 

 

5. 결과

Stack 사용

StringBuilder 사용

 

 

[추가]

Stack이나 List 구조를 사용하게 되면 마지막에 남은 원본 문자열을 순회해서 문자열 하나로 만들어야 하는 작업이 필요하다. 하지만 애초에 StringBuilder를 사용하면 toString() 메소드 하나로 바로 출력 결과를 만들 수 있기 때문에 간단하다.