[백준] 6198번: 옥상 정원 꾸미기

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

initial

after solving https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-2493%EB%B2%88-%ED%83%91-retry
this is a very similar question so i reused the template. Especially, I usually took care of the first element by taking it outside the main for loop logic but this way it is good.

I saved how many shorter towers we have encountered when we popped them off and append them to the new tall tower's tuple

care the BREAK or else it will recur infinitely

solution

from collections import deque

n = int(input())
lst = list(int(input()) for _ in range(n))
stack = deque()
ans = [0 for _ in range(n)]
count =0

for i in range(len(lst)-1,-1,-1):
    temp=0
    while stack:
        if stack[-1][0]<lst[i]:
            temp += stack[-1][1] +1
            stack.pop()
        else:
            break
    count+=temp
    stack.append((lst[i],temp))
print(count)

complexity

n time and space
The provided code calculates the total number of elements that are smaller than each element in the input list using a stack-based approach. Let's analyze the time and space complexity of this code:

1. Time Complexity:

   • The code uses a loop that iterates through the input list in reverse order (for i in range(len(lst)-1,-1,-1)). This loop iterates through all n elements, so it contributes O(n) to the time complexity.

   • Inside the loop, there's another while loop that iterates through the elements in the stack. In the worst case, the while loop can iterate through all elements in the stack before breaking out. In such a case, the inner while loop would also contribute O(n) to the time complexity.

   Therefore, the overall time complexity of the code is O(n).

2. Space Complexity:

   • The code uses a stack (stack) to store pairs of elements and their corresponding counts. The maximum number of elements that can be in the stack is bounded by n (the number of elements in the input list).

   Therefore, the space complexity of the code is O(n).

In summary, the code has a time complexity of O(n) and a space complexity of O(n), where n is the number of elements in the input list.