[Baekjoon] 9935: 문자열 폭발

문제

대상 문자열과 삭제할 문자열이 주어지면, 대상 문자열에서 삭제할 문자열이 더 이상 없을 때까지 계속 삭제해나가는 문제이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main9935 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine(); // 대상 문자열
        String deleteStr = br.readLine(); // 삭제할 문자열

        int strLength = str.length();
        int deleteStrLength = deleteStr.length();

        // 초기에 삭제할 문자열 길이만큼 대상 문자열을 StringBuilder에 삽입
        StringBuilder sb = new StringBuilder(str.substring(0, deleteStrLength));
        for (int i = deleteStrLength; i <= strLength; i++) {
            // StringBuilder에 있는 문자가 삭제할 문자열 길이보다 길고, 끝부분이 삭제할 문자열과 같다면 삭제 -> 즉 스택 pop연산과 동일
            while (sb.length() >= deleteStrLength &&
                    sb.substring(sb.length() - deleteStrLength).equals(deleteStr)) {
                sb.delete(sb.length() - deleteStrLength, sb.length());
            }

            if (i == strLength) {
                break;
            }

            // 끝에 문자를 하나씩 삽입
            sb.append(str.charAt(i));
        }

        if (sb.length() == 0) {
            System.out.println("FRULA");
            return;
        }
        System.out.println(sb);
    }
}

StringBuilder를 스택처럼 사용하여 구현하였다.

먼저 하나 씩 대상 문자열에서 문자를 추출하여 StringBuilder에 넣은 후, 끝 부분이 삭제할 문자열과 같은지 비교하며 삭제해 나갔다.

예를 들어, 대상 문자열이 nizCC44, 삭제할 문자열이 C4라고 한다면

n, ni, niz, nizC, nizCC 이렇게 계속 쌓이다가, nizCC4가 되면 끝 부분이 C4로 일치하기 때문에 삭제되어 nizC가 된다.

여기서 다시 마지막 인덱스 문자인 4가 삽입되어 nizC4가 되면 또 삭제되어 niz가 된다.

최종적으로 답은 niz가 된다.

 

회고

StringBuilder를 스택처럼 사용했지만 효율이 그렇게 좋지 않은 것 같다.

끝 부분에서 계속 subString하는 연산이 가볍지 않은 것 같다.

 

다른 방법을 이용하면 더 효율적으로 풀 수 있을 것 같다. 한 번 다시 풀어봐야겠다.