BOJ 3111 검열

https://www.acmicpc.net/problem/3111

문제

김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.

상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다.

1. T에 A가 없으면 알고리즘을 종료한다.
2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
3. T에 A가 없으면 알고리즘을 종료한다.
4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
5. 1번으로 돌아간다.

상근이는 마을을 지배해야하기 때문에, 검열을 할 시간이 없다. 상근이의 검열을 대신해주는 프로그램을 작성하시오.

---

입력

첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다.

---

출력

검열을 한 이후의 텍스트를 출력한다.

---

예제 입력 1

ne
lukanevolisarmu

예제 출력 1

lukavolisarmu

예제 입력 2

aba
ababacccababa

예제 출력 2

bacccab

… 이하 예제 생략

---

코드

이전에 풀었던 BOJ 9935 문자열 폭발 문제와 상당히 유사하다.

문자열 폭발 문제와의 차이점은 양쪽 끝에서 차례대로 문자열을 제거하는 것이다.

저번 문제에서는 스택의 get(int idx) 기능을 덱에서 사용하기 위해 덱을 LinkedList로 초기화하고 덱을 List로 형변환해서 get 메소드를 사용했지만, 생각해보니 매우 비효율적인 코드였다.

따라서 이번에는 덱을 ArrayDeque으로 초기화하고, 각 요소에 접근하기 위해 iterator를 사용했다.

하지만, 이번처럼 처음이나 끝에서 순차적으로 접근하는 것이 아닌 특정 인덱스에 접근해야 할 경우는 이전 방식처럼 하거나 스택을 사용하는 게 맞는 것 같다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine(), T = br.readLine();
        // T의 양쪽 끝에서 차례대로 문자열 A와 일치하는 부분을 삭제하고 남은 문자열을 출력하기 위해 두 개의 덱을 사용함
        // lDeq, rDeq은 각각 왼쪽과 오른쪽 부분을 검사하기 위한 덱이다
        Deque<Character> lDeq = new ArrayDeque<>(), rDeq = new ArrayDeque<>();
        // lIdx, rIdx는 문자열 T에서 검사 중인 왼쪽, 오른쪽 인덱스를 의미한다
        int lIdx = 0, rIdx = T.length() - 1;

        while (lIdx <= rIdx) {
            // T의 왼쪽 부분 검사
            while (lIdx <= rIdx) {
                // 문자열 T에서 검사할 lIdx 번째 문자를 lDeq에 추가한 후 lIdx++
                lDeq.offerLast(T.charAt(lIdx++));
                // 만약 lDeq에 A의 길이보다 작은 문자열만 있을 경우, 검사를 생략한다.
                if(lDeq.size() < A.length()) continue;
                // lDeq에 넣은 마지막 문자를 시작으로 해서 문자열 A와 동일한 문자열이 있는지 검사
                Iterator iterator = lDeq.descendingIterator();
                int checkIdx = 1;
                for (; checkIdx <= A.length() && (char) iterator.next() == A.charAt(A.length() - checkIdx); checkIdx++);
                // 만약 문자열 A와 동일한 문자열이 있을 경우, 해당 문자열을 제거
                if(checkIdx > A.length()) {
                    for (int i = 0; i < A.length(); i++) lDeq.pollLast();
                    break;
                }
            }

            // T의 오른쪽 부분 검사, 덱에 문자열을 저장, 삭제하는 순서를 제외하고 왼쪽 검사 부분과 동일한 코드이다.
            while (lIdx <= rIdx) {
                rDeq.offerFirst(T.charAt(rIdx--));
                if (rDeq.size() < A.length()) continue;
                Iterator iterator = rDeq.iterator();
                int checkIdx = 0;
                for (; checkIdx < A.length() && (char) iterator.next() == A.charAt(checkIdx); checkIdx++) ;
                if (checkIdx == A.length()) {
                    for (int i = 0; i < A.length(); i++) rDeq.pollFirst();
                    break;
                }
            }
        }
        
        StringBuilder answer = new StringBuilder();
        // 문자열 T의 모든 문자열을 검사한 후, lDeq과 rDeq에 남아있는 문자열을 합친다.
        while (!lDeq.isEmpty()) answer.append(lDeq.pollFirst());
        while (!rDeq.isEmpty()) answer.append(rDeq.pollFirst());
        
        // 두 덱에 남아있는 문자열을 합친 중간 부분에서 A 문자열과 동일한 부분이 검사될 경우, 계속 삭제해준다. 
        int AIdx = answer.indexOf(A);
        while (AIdx >= 0) {
            answer.delete(AIdx, AIdx + A.length());
            AIdx = answer.indexOf(A);
        }

        System.out.println(answer);
    }
}