[백준] 2504번: 괄호의 값 (MUST RETRY)

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

initial (indexError)

I placed the integer values in the stack of brackets, over complicating the logic. It also caused indexError, which I am not sure where it is caused

from collections import deque

hola = str(input())

if len(hola)==1 or len(hola)==0:
    print(0)
    exit()

stack = deque()
flag = False
count =0
for i in hola:
    if i in ['(', '[']:
        stack.append(i)
    else:
        if stack:
            if i==')':
                tmp = stack[-1]
                if tmp =='(':
                    stack.pop()
                    stack.append(2)
                elif tmp == '[':
                    flag = True
                    break
                #         if it is a number instead of ) or ]
                else:
                    lst =[]
                    hey=0
                    while stack:
                        if stack[-1] in ['(', '[']:
                            break
                        else:
                            lst.append(stack.pop())
                    for i in lst:
                        hey += i
                    if stack[-1]=='(':
                        hey*=2
                    elif stack[-1]=='[':
                        hey*=3
                    count += hey
                    stack.pop()
                    stack.append(hey)
            elif i==']':
                tmp=stack[-1]
                if tmp=='[':
                    stack.pop()
                    stack.append(3)
                #         if it is a number instead of ) or ]
                elif tmp == '(':
                    flag = True
                    break
                else:
                    lst =[]
                    hey=0
                    while stack:
                        if stack[-1] in ['(', '[']:
                            break
                        else:
                            lst.append(stack.pop())
                    for i in lst:
                        hey += i
                    if stack[-1]=='(':
                        hey*=2
                    elif stack[-1]=='[':
                        hey*=3
                    count += hey
                    stack.pop()
                    stack.append(hey)
ans =0
if flag== True:
    print(0)
else:
    for i in stack:
        if i in ['(','[',')',']']:
            print(0)
            exit()
        else:
            ans +=i
    print(ans)

solution

don't put integers in the stack of brackets and instead, assign a single variable =1 to mark whatever integers we have encountered.

it is very hard and i still kinda dont get how this single variable works and how this guy even thought of implementing this way

logic explained:
https://jie0025.tistory.com/175

retried feb 21st

I retried thinking of the implementation logic and still couldnt solve it. I think i didnt get the solution 4 months ago. But now i get it so hopefully i can solve next time.

Lets say we have (()[[]])([])
(() + [[]]) = 2 (2+33) = 2 2 + 23*3 = 4 + 18과 같다.
So instead of trying to solve from inside out, we can think of it as like expanding the brackets out so that we can solve easily by iterating from left to right.

So as we encounter open brackets, we multiply it by 2 or 3. When we encounter a closed bracket, if there is something in our stack and that last element in the stack is indeed a matching pair, we add whatever value we have accumulated to our answer and divide that accumulated value by 2 or 3. But if it is not a matching pair, we have encountered an invalid bracket pair so we make answer 0 and break out of the loop.

lastly even after iterating through all brackets and there is still some left in our stack, that means there are invalid pairs so we print 0 as answer. Else we print answer.

stack = [] # 스택
res = 1 # result에 더해주기 전 임시 변수
result = 0 # 결과 변수
p = list(input()) # 입력값

# 1~4번째 과정 시작
for i in range(len(p)):
    if p[i]=='(':
        res *= 2
        stack.append(p[i])

    elif p[i]=='[':
        res *= 3
        stack.append(p[i])

    elif p[i]==')':
        if not stack or stack[-1]!='(':
            result = 0
            break
        if p[i-1]=='(': result += res
        res //= 2
        stack.pop()

    elif p[i]==']':
        if not stack or stack[-1]!='[':
            result = 0
            break
        if p[i-1]=='[': result += res
        res //= 3
        stack.pop()


# 결과 출력
if stack:
    print(0)
else:
    print(result)

complexity

n time and space

The complexity of the provided code for evaluating the validity and calculating the score of parentheses and square brackets in a string is O(n), where n is the length of the input string p. Here's why:

1. The code iterates through each character in the input string p once, which takes O(n) time.

2. During the iteration, the code performs simple operations such as multiplication, division, and stack operations like appending and popping elements. These operations have constant time complexity, O(1).

3. Therefore, the overall time complexity of the code is O(n), as it depends linearly on the length of the input string.

4. The space complexity is also O(n) because the code uses a stack to store parentheses and square brackets, and in the worst case, the stack may contain all the characters from the input string.

So, the code has a linear time and space complexity, making it efficient for processing strings of reasonable lengths.