[백준] 4889번: 안정적인 문자열

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

initial

I am really weak at brackets questions idk why. So i instantly knew we have to use stack but I couldnt think of what logic. I first tried thinking like maybe making a check_validity function and if the accumulated string so far has a valid bracket pair we pop that bracket pair. But not only it is time inefficient bcos we have to check our accumulated string for each iteration of bracket in for loop (so def not o(n) time) but I dont think that will lead to a correct answer. That is cuz what if we have an enclosed valid bracket pair but in that bracket pair, we have an invalid pair? So something like {}}}{}. Anyway there is bound to be an easier pattern that I couldnt see so I googled.

The impt trick here is that in our stack, we always append the correct bracket, never }. That is cuz we are gonna pop { in our stack with incoming } whenever } is input. So when stack is empty and cur char is }, we increment ans (cuz we need to change that to {) and append { to our stack instead. But if stack is NOT empty and cur char is }, we are BOUND to have a valid pair since we declared to only input { into our stack so we pop the topmost char from our stack since it is a valid pair. Else, if it is {, we just append that to our stack.

Now what if there are too many { in the string? We need to turn half of them into } to make it a valid bracket pair so if stack is not empty (which means there are unmatched {s), then we increment ans via half the length of the stack.

oh another good trick is this enumerate and its start parameter, which we should initialise to 1 since we have to print from 1 onwards, not 0-indexed.

solution

from collections import deque

lst = []
while True:
    string = input()
    ans = 0
    stack = deque()
    
    if '-' in string:
        break

    for i in range(len(string)):
        hola = string[i]
        if not stack and hola == '}':
            ans += 1
            stack.append('{')
        elif stack and hola == '}':
            stack.pop()
        else:
            stack.append(hola)

    ans += len(stack) // 2
    lst.append(ans)

for i, v in enumerate(lst, start=1):
    print(f"{i}. {v}")

complexity

Let's analyze the time and space complexity of the corrected code:

Time Complexity:

1. While Loop:

   • The while loop continues until a string containing a hyphen ('-') is encountered. In the worst case, it could iterate through all strings, resulting in (O(N)) iterations, where (N) is the total length of all input strings combined.

2. For Loop:

   • The for loop iterates through each character in the input string. In the worst case, it iterates through all characters in all input strings, resulting in (O(M)) iterations, where (M) is the total number of characters in all input strings combined.

3. Overall Time Complexity:

   • The overall time complexity is (O(N \cdot M)), where (N) is the number of input strings, and (M) is the total number of characters in all input strings combined.

Space Complexity:

1. Stack:

   • The space used by the stack is proportional to the maximum depth of nested braces. In the worst case, the depth could be equal to the total number of characters in all input strings combined, resulting in (O(M)) space complexity.

2. lst List:

   • The list 'lst' stores the results for each input string, resulting in (O(N)) space complexity.

3. Overall Space Complexity:

   • The overall space complexity is (O(M + N)).

Note:

• The space complexity can be affected by the worst-case scenario where all opening braces remain unmatched until the end of each string.

Please keep in mind that these analyses are based on the worst-case scenarios. The actual time and space complexity can be lower in practice, depending on the characteristics of the input.