Seongkyun Han's blog

190228 백준 알고리즘 문제풀기

28 Feb 2019 | baekjoon

[2504] 괄호의 값

문제

  • 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
    • 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
    • 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
    • X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
  • 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
    • ‘()’ 인 괄호열의 값은 2이다.
    • ‘[]’ 인 괄호열의 값은 3이다.
    • ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
    • ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
    • 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

  • 예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

  • Stack을 이용하여 문제를 푼다.
    • 괄호가 열릴 때 스택에 넣는다.(push)
      • t(temp)를 1로 선언 후 ‘(‘일때는 2, ‘[‘일때는 3을 곱한다.
      • 괄호가 열린다는 의미는 바로 안에 있는 괄호에 대한 값과 곱해짐을 의미하기 때문이다.
    • 괄호가 닫일 때 스택에서 뺀다.(pop)
      • 바로 전 인덱스의 괄호가 맞는 쌍일 경우 결과를 더해준다.
      • ’(‘일 경우 t/2를, ‘[‘일 경우 t/3을 수행한다.
    • 시간단축을 위해 w(wrong) 변수를 선언하고, 불가능한 경우 중간에 빠져나간다.(break)

정답

class Stack:
    def __init__(self):
        self.len = 0
        self.list = []

    def push(self, num):
        self.list.append(num)
        self.len += 1

    def pop(self):
        if self.size() == 0:
            return -1
        pop_result = self.list[self.len-1]
        del self.list[self.len-1]
        self.len -= 1
        return pop_result

    def size(self):
        return self.len

    def empty(self):
        return 1 if self.len == 0 else 0

    def top(self):
        return self.list[-1] if self.size() != 0 else -1

stack = Stack()
result = 0
t = 1
s = 0
w = False
ps = list(input())
for j in range(len(ps)):
    if ps[j] == '(':
        t *= 2
        stack.push('(')
    elif ps[j] == '[':
        t *= 3
        stack.push('[')
    elif ps[j] == ')':
        if ps[j-1] == '(':
            s += t
        if stack.empty():
            w = True
            break
        if stack.top() == '(':
            stack.pop()
        t /= 2
    else:
        if ps[j-1] == '[':
            s += t
        if stack.empty():
            w = True
            break
        if stack.top() == '[':
            stack.pop()
        t /= 3
if w or stack.empty() == 0:
    print(0)
else:
    print(int(s))

Related Posts