[백준] 1541번: 잃어버린 괄호

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

initial

I initially felt it is similar to https://velog.io/@whitehousechef/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%98%EC%8B%9D-%EC%B5%9C%EB%8C%80%ED%99%94-retry

but simpler.

I was surprisingly able to finally solve a stack question (actually not really a stack but it is a greedy question).

The logic is as such:
we wanna extend our bracket from - to to the next +. What I mean is if we have

-30+50+70-20+30

the way to minimise this sum is to make the postives as small as poss and negatives as big as poss.

so bracket would be something like

-(30+50+70)-(20+30) = -something

So when we meet a minus operator, we can assume that any numbers after that minus operator - be it positive or negative, will subtract our sum.

An exception is if there is a positive number before a minus operator is met like

55-50+40

Then we can't make 55 negative lol. So there is no choice but to add 55 first. But once we meet - after that, we can minus any number that follows suit.

I used a boolean flag to mark the point where we meet a minus operator.

isinstance(something, int)

isinstance(sth, int) is a boolean function that checks if something is a integer type. chatgpt recommended this

solution

from collections import deque

n = input()
tmp = ''
queue = deque()
ans = 0
flag = True

for i in n:
    if i.isdigit():
        tmp += i
    else:
        if tmp:
            queue.append(int(tmp))
            tmp = ''
        queue.append(i)

if tmp:
    queue.append(int(tmp))

while queue:
    i = queue.popleft()
    if isinstance(i, int):
        if flag:
            ans += i
        else:
            ans -= i
    elif i == '-':
        flag = False

print(ans)

revisited jan 25th

yes so as soon as we see a minus sign we can just minus all the numbers. So using that queue to append integers and operators (+ and -) into our queue, and not forgetting that if tmp is not empty after traversing, we have to add that too.

Then while queue, as soon as we see a minus, we flag it. Using ifinstance(something,int) we can check if the element that we just popped is an int.

complexity

n time and space?
The time complexity of this code is O(n), where n is the length of the input string.

The space complexity is O(m), where m is the number of integer values extracted from the input string and stored in the queue. In the worst case, every character in the input string is a digit, and each digit is appended to the queue, so m can be at most n/2 (since there are non-digit characters in the string).