[BOJ][Gold V] 괄호 제거 - 2800 (Kotlin)

[Gold V] 괄호 제거 - 2800

문제 링크

2800번: 괄호 제거

분류

브루트포스 알고리즘, 자료 구조, 스택, 문자열

문제 설명

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

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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. 괄호 쌍을 찾아 리스트로 저장한다.
2. 가능한 모든 괄호쌍의 조합을 찾아 해당하는 문자열을 기록한다.

문자열을 기록하는 자료구조는 중복되어서는 안되며, 정렬되야 한다. 고로 TreeSet을 사용하는 것이 매우 타당한 선택으로 생각된다.

입력

var pairs = ArrayList<Pair<Int, Int>>()
val line = readln()
val st = LinkedList<Int>()

line.forEachIndexed { idx, c ->
    when(c) {
        '(' -> st.push(idx)
        ')' -> pairs.add(Pair(st.pop(), idx))
    }
}

stack을 하나 만들어서 괄호 쌍을 모두 찾아 기록해준다.

조합

// in main()
selectPairs(0, ArrayList())

...

fun getExpr(exceptList : List<Int>) : String {
    val sb = StringBuilder()
    repeat(line.length) {
        if(it !in exceptList) sb.append(line[it])
    }
    return sb.toString()
}


fun selectPairs(idx: Int, selected: ArrayList<Int>) {
    if(idx == pairs.size) return

    answers.add(getExpr(selected))
    selectPairs(idx+1, selected)

    selected.add(pairs[idx].first)
    selected.add(pairs[idx].second)
    answers.add(getExpr(selected))
    selectPairs(idx+1, selected)
    selected.removeLast()
    selected.removeLast()

}

kotlin/ java 는 parameter가 레퍼런스다. C++과 다르게 전달 받은 값이 깊은 복사가 아님을 유의.
C++ 처럼 하고 싶다면 selected.clone() 해서 넘겨주면 됨.

위 코드는 pair를 재귀로 돌며 괄호 조합을 찾아 answer에 기록하는 코드.

출력

val sb = StringBuilder()
answers.forEachIndexed { idx, it ->
    if(idx!=0) sb.appendLine(it)
}
println(sb.toString())

출력해야하는 문자열이 많으니까 StringBuilder를 활용해주자.
문제에서 진부분집합을 요구함으로 headSet을 빼고 append해주었다.

코드