#2504 괄호의 값

문제

---

 

 

코드

---

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine()
    val s = Stack<Char>()
    var temp = 1
    var result = 0
    for (i in input.indices) {
        when (input[i]) {
            '(' -> {
                s.push('(')
                temp *= 2
            }

            '[' -> {
                s.push('[')
                temp *= 3
            }

            ')' -> {
                if (s.isNotEmpty() && s.peek() == '(') {
                    if (input[i - 1] == '(') result += temp
                    s.pop()
                    temp /= 2
                } else {
                    s.push(')')
                }
            }

            ']' -> {
                if (s.isNotEmpty() && s.peek() == '[') {
                    if (input[i - 1] == '[') result += temp
                    s.pop()
                    temp /= 3
                } else {
                    s.push(']')
                }
            }
        }
    }
    if (s.isNotEmpty()) println(0)
    else println(result)
}

 

 

풀이

---

문제에서 정의된 규칙

 

처음 생각한 방법

• 열린 괄호가 왔을 땐, 해당 괄호를 스택에 push
• 닫힌 괄호가 왔을 때
  • stack의 top이 숫자인지 확인
    • 숫자라면, 열린 괄호를 찾을 때까지 pop하면서 숫자를 전부 더한 후 숫자(2또는 3)를 곱한 후 push
      • 즉, 괄호열을 계산하여 push한다는 의미로 문제에서 정의된 규칙의 3, 4번에 해당함
    • 숫자가 아니라 바로 열린 괄호가 온다면, pop하고, 숫자(2 또는 3)를 push
      • 문제에서 정의된 규칙의 1, 2번에 해당함
• 위 과정을 괄호를 전부 확인할 때까지 반복
• 스택에 남아있는 숫자를 전부 더한 값이 결과 값
• 만약 스택에 괄호가 남아있다면 0을 출력 -> 쌍을 이루지 못했다는 의미

즉, 스택에는 괄호와 숫자가 같이 입력된다.

 

 

위 방식대로 풀이를 작성했다.

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine()
    val s = Stack<Any>()
    var result = 0
    for (c in input) {
        var temp = 0
        when (c) {
            '(', '[' -> s.push(c)
            else -> {
            	val multi = if (c == ')') 2 else 3
                val openBracket = if (c == ')') '(' else '['
                while (s.isNotEmpty() && s.peek() is Int) {
                    temp += s.pop() as Int
                }
                temp = if (temp == 0) multi else temp * multi
                if (s.isNotEmpty() && s.peek() == openBracket) {
                    s.pop()
                    s.push(temp)
                } else s.push(c)
            }
        }
    }
    for (element in s) {
        if (element is Int) result += element.toInt()
        else {
            result = 0
            break
        }
    }
    println(result)
}

이렇게 작성해도 백준에서는 제대로 정답 처리가 된다

 

다른 사람의 풀이가 궁금하여 코드를 둘러보던 중,

더 간단한 방식으로 푼 사람이 있어서 그 사람의 코드를 분석하고 있었다.

 

이해가 잘 안가서 해당 문제를 구글링해보니까 내가 보고 있는 코드와 유사한 방법으로 푼 사람들이 많더라.

그래서 블로그들을 정독하다가, 내가 위에 작성한 코드의 문제점을 발견했다.

 

https://loosie.tistory.com/349

[BOJ] 백준 2504번 괄호의 값 (Java)

이 블로그에서 발견한 반례를 입력하니까 나도 오답이 출력됐다.

 

반례) (((()))(([])))(([[]]))[]() 

아스키코드 40, 41이 열린 괄호를 나타내기 때문에 오류가 발생한 것이다.

앞의 (((()))(([]))) 까지 계산 결과가 40인데, 이것이 '(' 로 판단되어 문제가 발생한 것

 

아스키코드 표 참고

 

백준에서는 문제가 없다 해도, 제대로 된 방식으로 풀고 싶었다.

그래서 다른 방식으로 풀어봤다. 

 

이 방식이 처음에 이해가 잘 안 갔는데, 다른 사람들의 풀이 부분을 보면 분배법칙에 대해 얘기하고 있다.

( [ ( ) ] )

이 괄호를 예로 들면, (2 * (3 * 2)) 의 순서로 계산 하는 것이 아니라, 2 * 3 * 2 이런 식으로 앞에서부터 계산 하는 것이다.

말이 이해가 잘 안될 수 있는데, 제일 안쪽의 괄호부터 계산하는 것이 아니라, 열린 괄호가 나오면 그 때 바로 계산을 해주는 것이다.

 

이게 여러 괄호가 중첩되어있다면 분배법칙이라고 하는 말이 더 와닿을 것이다.

나도 여러 괄호가 중첩되어있는 케이스를 보고 어떤 말인지 이해하게 됐다.ㅋㅋ

( [ ] ( [ ] ) )

이런 경우를 예로 들어보자

분배법칙 의미

이런 느낌인 것이다.

 

따라서 열린 괄호로 판단하면 쉽게 해결 할 수 있다는 것이다.

tmp 값을 두고, 열린 괄호가 오면 2 또는 3을 곱해준다.

닫힌 괄호가 왔을 때, 올바른 괄호열이라고 판단되면 2 또는 3을 나눠준다.

이렇게 하면 중첩된 괄호를 제대로 계산할 수 있게 된다.

 

이 로직을 바탕으로 코드를 작성했다.

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine()
    val s = Stack<Char>()
    var temp = 1
    var result = 0
    for (i in input.indices) {
        when (input[i]) {
            '(' -> {
                s.push('(')
                temp *= 2
            }

            '[' -> {
                s.push('[')
                temp *= 3
            }

            ')' -> {
                if (s.isNotEmpty() && s.peek() == '(') {
                    if (input[i - 1] == '(') result += temp
                    s.pop()
                    temp /= 2
                } else {
                    s.push(')')
                }
            }

            ']' -> {
                if (s.isNotEmpty() && s.peek() == '[') {
                    if (input[i - 1] == '[') result += temp
                    s.pop()
                    temp /= 3
                } else {
                    s.push(']')
                }
            }
        }
    }
    if (s.isNotEmpty()) println(0)
    else println(result)
}

아까보다 훨씬 간단해진 느낌이다.

여기서 헷갈리면 안 되는 것이 실제로 연속된 괄호열인지, 아닌지를 구별하는 것이다.

닫힌 괄호열이 왔을 때

• 스택은 괄호가 쌍을 이루는 것이 맞는지(올바른 괄호열인지) 확인하기 위해서고,
• 실제 문자열은 연속된 괄호열인지 확인하는 용도이다.
  • 실제로 우리는 열린 괄호가 왔을 때 계산을 먼저 했기 때문에 연속된 괄호열이 온다면 더 이상 계산을 하면 안되는 것이다.
  • 예를 들어 ( [ [ ] ] ) 의 경우, '(' 를 보고 *2, '['를 보고 *3, '['를 보고 *3을 해줬기 때문에 닫힌 괄호가 왔을 때, 또 계산(곱셈)을 하게 된다면 중복된 계산을 하게 되는 것이다.
  • 즉, 연속된 괄호열이 온다면, 분배법칙을 하는 하나의 항이 끝났다는 것임(위쪽의 분배법칙을 설명하는 사진에서 빨간 줄 부분)
  • 따라서 이때는 result 값에 지금까지의 계산 결과인 tmp 값을 더하면 된다.

 

이해하는데 조금 어려움을 겪었다.

그래서 디버깅을 좀 많이 했던 것 같다.

다른 사람들도 내 풀이를 보고 이해할 수 있으면 좋겠다!