2800번: 괄호 제거

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

2800번: 괄호 제거

언어 : Kotlin

 

문제 설명 :

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

 

입력 :

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

 

출력 :

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

입출력 예 :

입력	출력
(0/(0))	(0/0) 0/(0) 0/0
(2+(2*2)+2)	(2+2*2+2) 2+(2*2)+2 2+2*2+2
(1+(2*(3+4)))	(1+(2*3+4)) (1+2*(3+4)) (1+2*3+4) 1+(2*(3+4)) 1+(2*3+4) 1+2*(3+4) 1+2*3+4

 

풀이 : 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

var result = TreeSet<String>()

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

    val input = readLine()
    val stack = Stack<Int>()
    val arr = ArrayList<Pair<Int, Int>>()
    input.forEachIndexed { index, c ->
        when (c) {
            '(' -> stack.push(index)
            ')' -> arr += Pair(stack.pop(), index)
        }
    }
    combination(0, arr.size, input, arrayListOf(), arr)

    val sb = StringBuilder()
    result.forEachIndexed { index, s ->
        if (index != 0) sb.appendLine(s)
    }

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

fun combination(idx: Int, depth: Int, input: String, cur: ArrayList<Int>, arr: ArrayList<Pair<Int, Int>>) {
    if (idx == depth) {
        return
    } else {
        result += addList(input, cur)
        combination(idx + 1, depth, input, cur, arr)
        cur += arr[idx].first
        cur += arr[idx].second

        result += addList(input, cur)
        combination(idx +1, depth, input, cur, arr)
        cur.removeLast()
        cur.removeLast()
    }
}

fun addList(input: String, cur: List<Int>): String {
    val sb = StringBuilder()
    repeat(input.length) {
        if (it !in cur) sb.append(input[it])
    }

    return sb.toString()
}