BOJ 2504번: 괄호의 값

www.acmicpc.net/problem/2504

2504번: 괄호의 값

아이디어:

스택을 이용하면 될 것 같은데. 앞서 풀었던 괄호 문제랑 비슷하게.

스택을 만들고 왼쪽 괄호인 경우에는 push, 오른쪽 괄호인 경우에는 스택의 하나를 pop한다.

이때 pop한 값이 왼쪽 괄호이고 짝이 맞으면 조건에 맞게 숫자를 push해야 되는데, 이때 스택에 남아 있는 값이 뭔지 peek해보고(값이 남아있지 않을 경우 예외처리 해줘야 함), 숫자가 있으면 그것도 pop해서 더한 후 숫자를 push한다.

pop한 값이 숫자이면 하나를 더 pop해서 짝이 맞으면 해당하는 조건에 맞게 숫자를 계산하고(이때도 스택 비었는지 확인), 스택에 남아 있는 값을 peek해서 숫자면 그것도 pop해서 더한 후 숫자를 push한다.

 

이때, 각각의 경우에 짝이 안맞는 경우 flag=False로 바꾸고 break 해준다.

맨 마지막에도 stack의 길이가 1이 아니면 flag=False로 바꾼다.

 

import sys
st = list(sys.stdin.readline().rstrip())
stack = []
flag = True

for s in st:
    #왼쪽 괄호인 경우 push
    if (s=="(" or s=="["):
        stack.append(s)
        
    #오른쪽 괄호인 경우
    else:
        #짝이 안맞는 경우-왼쪽 괄호가 부족
        if (len(stack)==0):
            flag = False
            break
        
        p1 = stack.pop()

        #괄호 사이에 숫자가 있는 경우
        if (p1!="(" and p1!="["):
            
            if (len(stack)==0):
                flag = False
                break
            
            p2 = stack.pop()

            if (s==")" and p2=="("):
                push = 2*p1
                if (len(stack)!=0):
                    p3 = stack[-1]
                    #스택에 숫자가 남아있으면 둘을 더한 값을 push
                    if (p3!="(" and p3!="["):
                        push += stack.pop()
                stack.append(push)
        
            elif (s=="]" and p2=="["):
                push = 3*p1
                if (len(stack)!=0):
                    p3 = stack[-1]
                    #스택에 숫자가 남아있으면 둘을 더한 값을 push
                    if (p3!="(" and p3!="["):
                        push += stack.pop()
                stack.append(push)

            #짝이 안맞는 경우    
            else:
                flag = False
                break
            
        
        elif (s==")" and p1=="("):
            push = 2
            if (len(stack)!=0):      
                p2 = stack[-1]
                #스택에 숫자가 있으면 둘을 더한 값을 push
                if (p2!="(" and p2!="["):
                    push += stack.pop()
            stack.append(push)
        
        elif (s=="]" and p1=="["):
            push = 3
            if (len(stack)!=0):
                p2 = stack[-1]
                #스택에 숫자가 있으면 둘을 더한 값을 push
                if (p2!="(" and p2!="["):
                    push += stack.pop()
            stack.append(push)

        
        #짝이 안맞는 경우
        else:
            flag = False
            break
if (len(stack)!=1):
    flag = False
if (flag==False): print(0)
else: print(stack.pop())

※괄호 사이에 숫자가 있는 경우에서 stack이 비어있는지 확인을 다시 해줘야 한다.

 

 

---

그리고 이건 저번 알고리즘 캠프때 풀었던 코드인 것 같은데 훨씬 깔끔하긴 하다. 근데 이런 방식을 생각해내는 게 어려울 것 같다.ㅠㅠ 그리고 숫자를 더하는 건 맨 마지막에 한 번에 해도 되네.. 아냐 내가 푼 방식에서 더하는 것만 바꾸면 안된다.. 암튼 코드 단순화 할 수 있을 것 같다.

import sys
arr=sys.stdin.readline().rstrip()
stack=[]
for i in arr:
    temp=0
    if i=='[':
        stack.append(-3)
    elif i=='(':
        stack.append(-2)
    elif i==']':
        while True:
            if len(stack)==0:
                print(0)
                sys.exit(0)
            top=stack.pop()
            if top>0:
                temp+=top
            elif top==-2:
                print(0)
                sys.exit(0)
            elif top==-3:
                if temp==0:
                    temp=1
                stack.append(temp*3)
                break
    elif i==')':
        while True:
            if len(stack)==0:
                print(0)
                sys.exit(0)
            top=stack.pop()
            if top>0:
                temp+=top
            elif top==-3:
                print(0)
                sys.exit(0)
            elif top==-2:
                if temp==0:
                    temp=1
                stack.append(temp*2)
                break
answer=0
while len(stack)>0:
    top=stack.pop()
    if top<0:
        print(0)
        sys.exit(0)
    answer+=top
print(answer)

이건 동아리에서 다른 부원이 푼 방식인데, 아주 깔끔하고 좋아서 가져왔다.

---

210722

다시 풀어봤는데.. 코드 길이는 줄었고 지금 내가 보기엔 더 이해하기 쉬운 것 같지만 시간은 비슷하거나 조금 더 걸린다ㅎ 그리고 스택이 비어있는 경우와 스택에 왼쪽 괄호가 남아있는 경우 처리를 빼먹어서 런타임 에러가 났었다. 항상 가능한 모든 경우를 생각하고 풀자.

import sys

string = list(sys.stdin.readline().rstrip())
st = []
flag = True

for i in string:
    if (i == '(' or i == '['):
        st.append(i)
    else:
        num = 0
        while (len(st)!=0 and st[-1]!='(' and st[-1]!='['):
            num += st.pop()
            
        if (len(st)==0):
            flag = False
            break
        
        if (i==')' and st.pop()=='('):
            if (num==0):
                st.append(2)
            else:
                st.append(num*2)
                
        elif (i==']' and st.pop()=='['):
            if (num==0):
                st.append(3)
            else:
                st.append(num*3)
                
        else:
            flag = False
            break
ans = 0      
for i in st:
    if (i=='(' or i=='['):
        flag = False
        break
    ans += i

if (flag==False):
    print(0)
else: print(ans)