3111번: 검열

문제 출처 : https://www.acmicpc.net/problem/3111

 

언어 : Kotlin

 

문제 설명 :

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

상근이는 텍스트 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.5초 (추가 시간 없음)
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
ne lukanevolisarmu	lukavolisarmu
aba ababacccababa	bacccab
banana babananananadeda	deda

 

다른 사람의 풀이 : 

좌, 우 스택 총 2개를 사용한다

1. 좌 스택은 텍스트의 시작부분부터 스택에 넣으며 a 패턴을 발견하면 스택에서 제거한다.
2. 우 스택은 텍스트의 마지막부분부터 스택에 넣으며 a 패턴을 발견하면 스택에서 제거한다.
3. 텍스트를 전부 돌았다면 왼쪽 스택에 있는 것을 오른쪽 스택으로 옮긴 뒤, 오른쪽 스택에서 a 패턴을 발견하면 지운다.

위 1 ~ 3번 과정이 seacrhAndDelete 함수의 while문 1회치 과정이다.

이 while문 1회치 과정은 문제의 1 ~ 5번 과정을 전부 포함하고 있다.

 

https://dundung.tistory.com/94

백준 3111 검열 Java

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.properties.Delegates

val left = Stack<Char>()
val right = Stack<Char>()
var start = 0
var end by Delegates.notNull<Int>()
var isRemove = false

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val a = readLine()
    val t = readLine()
    end = t.length - 1

    val sb = searchAndDelete(a, t)

    while (true) {
        val idx = sb.indexOf(a)
        if (idx < 0) break
        sb.delete(idx, idx + a.length)
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
}

fun searchAndDelete(a: String, t: String): StringBuilder {
    while (start <= end) {
        if (!isRemove) {
            left.push(t[start++])
            if (left.size >= a.length && left.peek() == a[a.lastIndex]) {
                var temp = a.lastIndex
                var check = true
                for (j in left.lastIndex downTo left.size - a.length) {
                    if (left[j] != a[temp--]) {
                        check = false
                        break
                    }
                }

                if (check) {
                    isRemove = true
                    for (j in a.indices) {
                        left.pop()
                    }
                }
            }
        }

        if (isRemove && start <= end) {
            val aReverse = StringBuilder(a).reverse().toString()
            right.push(t[end--])
            if (right.size >= a.length && right.peek() == aReverse[a.lastIndex]) {
                var temp = a.lastIndex
                var check = true
                for (j in right.lastIndex downTo right.size - a.length) {
                    if (right[j] != aReverse[temp--]) {
                        check = false
                        break
                    }
                }

                if (check) {
                    isRemove = false
                    for (j in a.indices) {
                        right.pop()
                    }
                }
            }
        }
    }

    val leftSize = left.size
    for (i in 0 until leftSize) {
        right.push(left.pop())
    }

    val sb = StringBuilder()
    while (!right.isEmpty()) {
        sb.append(right.pop())
    }

    return sb
}