백준 2504 괄호의 값 - [알고리즘] [kotlin]

문제 내용

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

 

문제 분석

1. 괄호는 [] ()로 2종류가 존재함

2. 괄호 안에 괄호가 있을 수 있다.

3. 안쪽 괄호는 바깥 괄호가 닫히기 전 닫혀야 한다.
즉, 닫히는 괄호가 들어올 때, 가장 최근 열린 괄호와 종류가 같아야 한다.

4. 괄호 안에 있는 값들에 곱연산을 한다.

5. 포함관계가 없는 괄호들은 합연산을 한다.

 

아이디어

1. stack을 이용해 가장 최근 열린 괄호와, 이번에 들어온 괄호의 종류를 비교할 수 있다.

2. 숫자가 붙어있을 경우 바로 합연산을 진행해도 무관하다.

 

풀이

1. push 및 내부 과정을 MyStack 클래스에 위임함

2. 매번 계산을 거치기 때문에 0~9를 넘을 수 있음

때문에, Int or String 자료형을 Stack에 사용함

3. push시 닫히는 괄호에 대해 곱 or 합연산을 진행 후 stack에 넣음

4. 받은 입력의 유효성을 매번 체크함

import java.util.*

class MyStack {

    // -4:(  -3:[  -2:)  -1:]  -5:err
    private val stack = LinkedList<Int>()

    fun getAnswer(): Int{
        // 숫자 외의 문자가 남아있다면 잘못된 String으로 0을 출력한다.
        var sum = 0
        stack.forEach {
            if(isDigit(it).not()) return 0
            sum += it
        }

        return sum
    }

    // 도중에 잘못된 문자열임이 판단되면 false를 반환한다.
    fun push(charValue: Char): Boolean {
        val value = convertIfLetter(charValue)
        if(isOpen(value)) {
            // 열리는 괄호는 그냥 넣는다.
            stack.addLast(value)
        } else {
            // 닫히는 괄호는 숫자가 아닌 char가 나올때까지 뺀 후 판단.
            val tmpStack = LinkedList<Int>()
            while(true) {
                if(stack.isEmpty()) return false
                if( isDigit(stack.last).not() ) break
                tmpStack.addLast(stack.removeLast())
            }
            // 유효한지 판단
            if(checkValid(stack.last, value).not()) return false
            // 적용할 값
            val applyValue = if(value == -1) 3 else 2
            // 기존 값
            val origin = if(tmpStack.isEmpty()) 1 else tmpStack.sum()

            // 열린 괄호를 제거 후 값 삽입
            stack.removeLast()
            stack.addLast(applyValue*origin)
        }

        return true
    }

    private fun convertIfLetter(value: Char): Int {
        return when(value) {
            '(' -> -4
            '[' -> -3
            ')' -> -2
            ']' -> -1
            else -> value.digitToIntOrNull() ?: -5
        }
    }

    private fun isDigit(value: Int): Boolean {
        return value >= 0
    }

    private fun isOpen(value: Int): Boolean {
        return value <= -3
    }

    private fun checkValid(open: Int, close: Int): Boolean {
        return (open == -4 && close == -2) || (open == -3 && close == -1)
    }

}

fun main() {
    val str = readln()
    val myStack = MyStack()
    str.forEach { char ->
        val check = myStack.push(char)
        if(check.not()) {
            println(0)
            return
        }
    }
    println(myStack.getAnswer())
}