[BOJ] 9935 - 문자열 폭발

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

난이도: 골드 4

사용언어: JAVA

 

풀이

저는 이 문제를 Deque를 사용하여 해결했습니다. Deque는 스택과 큐를 합쳐놓은 형태로, 배열의 앞 뒤로 모두 입출력이 가능한 형태입니다. 폭발 문자열을 찾아낼 때는 스택이, 폭발 문자열이 아님을 확인하고 그대로 출력할 때는 큐가 필요하여 Deque를 사용했습니다.

 

또한 Deque를 사용할 때도, 해당 문자와 해당 문자가 폭발 문자열에서 몇 번째 글자인지를 모두 사용하기 위해 class를 이용하였습니다.

 

풀이는 다음과 같습니다.

 

1. 문자열을 처음부터 끝까지 탐색한다.

2. 탐색하는 동안 폭발 문자열의 첫 글자와 같은 글자가 있으면 Deque에 삽입한다.

3. 폭발 문자열을 만들 수 있는 다음 글자가 들어오면 또 Deque에 삽입해준다.

4. Deque 내에서 폭발 문자열이 만들어지면 해당 폭발 문자열을 삭제해준다.

5. 폭발 문자열과 상관없는 글자가 들어오면 현재 Deque에 있는 모든 글자를 출력해주고 비워준다.

 

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
 
class Main {
 
    static String s1;
    static String s2; // 폭발 문자열
 
    static public class element {
        char ch;
        int order;
 
        public element(char ch, int order) {
            this.ch = ch;
            this.order = order;
        }
    }
 
    static Deque<element> dq = new ArrayDeque<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int k = 0;
        int frula = 0;
 
        s1 = br.readLine();
        s2 = br.readLine();
        if (s2.length() == 1) { // 예외 케이스: 폭발 문자열이 1글자 문자열일 경우
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) != s2.charAt(0)) {
                    bw.write(s1.charAt(i));
                    frula = 1;
                }
            }
            if (frula == 0)
                bw.write("FRULA\n");
            bw.flush();
            bw.close();
            br.close();
            System.exit(0);
        }
 
        for (int i = 0; i < s1.length(); i++) { // 문자열을 처음부터 끝까지 확인하면서,
            if (s1.charAt(i) == s2.charAt(0)) { // 폭발 문자열의 첫 글자와 같으면
                dq.push(new element(s2.charAt(0), 0)); // dq에 삽입
                k = 1; // k는 다음 글자가 폭발 문자열에서 몇번째 글자가 와야하는지 표시
            } else if (s1.charAt(i) == s2.charAt(k)) { // 폭발 문자열을 만들 수 있는 문자가 들어오면,
                dq.push(new element(s2.charAt(k), k)); // dq에 삽입
                k++;
 
                if (k >= s2.length()) { // 폭발 문자열이 만들어졌으면
                    while (dq.pop().ch != s2.charAt(0)) ; // 폭발 문자열을 dq에서 제거
 
                    if (dq.isEmpty()) k = 0; // 제거하고 나니 dq가 비었다면 k = 0
                    else k = dq.peek().order + 1; // 그렇지 않다면 k = top에 있는 글자의 순번 +1
                }
            } else { // 폭발 문자열과 상관없는 글자가 들어온다면
                dq.push(new element(s1.charAt(i), 0));
                while (!dq.isEmpty()) { // dq가 빌 때 까지 모두 출력
                    bw.write(String.valueOf(dq.pollLast().ch));
                    frula = 1;
                }
                k = 0;
            }
        }
        while (!dq.isEmpty()) { // dq에 남은 글자 모두 출력
            bw.write(String.valueOf(dq.pollLast().ch));
            frula = 1;
        }
        if (frula == 0) { // 만일 한번도 출력할 글자가 없었다면
            bw.write("FRULA\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

사용한 테스트 케이스로는

 

1235126734123123412344

1234

 

112341234123123441234235

1234

 

aaabba

ab

 

bbbb

b

가 있습니다.