[백준] 2812번: 크게 만들기

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

initial

First i was like dafuq how do you solve this. But I sat quietly and thought for like 15 minutes until I realised i can implement a greedy pattern. When we iterate each number in that string number, if it is bigger than the previous stored numbers in our stack, we should pop them and decrement k and append our big number instead cuz we want the largest starting numbers.

I also thought i would get some leftover k if this greedy pattern is implemented like 732 and k=2. That impl will give us 732 but we need to delete 2 numbers. So if there are leftover k, we slice them from the back cuz we know the back numbers would have stored the low numbers like 1 and 2 cuz if there were high values like 9 or 8, our pattern would have caught it and would have removed those low numbers.

My initial approach was around 3000ms but i saw others was like 300ms. I looked and saw i am unnecessarily building my result string by popping each element in our stack and reversing the result string. We dont have to reverse string as stack is basically a list so we slice leftover k from the back and we can just iterate the elements with a for loop.

initial 3000ms

n, k = map(int, input().split())
number = input()

stack = [number[0]]

for i in range(1, n):
    num = number[i]
    while stack and stack[-1] < num and k:
        stack.pop()
        k -= 1
    stack.append(num)

result = ""
while stack:
    result += stack.pop()

result=result[::-1]
if k:
    result = result[:-k]

print(result)

final 300ms

n, k = map(int, input().split())
number = input()

stack = [number[0]]

for i in range(1, n):
    num = number[i]
    while stack and stack[-1] < num and k:
        stack.pop()
        k -= 1
    stack.append(num)

while k:
    k-=1
    stack.pop()

for i in stack:
    print(i, end='')

complexity

n time and space?
yep

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

1. Time Complexity:

   • Constructing the initial stack: O(n)
     • The for loop iterates through each character of the input string, resulting in O(n) time complexity.
   • Removing k elements from the end of the stack: O(k)
     • The while loop runs k times, each time performing a constant time operation of popping an element from the stack.
   • Printing the elements of the stack: O(n)
     • The for loop iterates through each element of the stack, resulting in O(n) time complexity.

   Overall, the time complexity is dominated by the linear time complexity of constructing the initial stack and printing its elements. Hence, the overall time complexity is O(n).

2. Space Complexity:

   • Stack: O(n)
     • The stack can potentially store up to n elements, where n is the length of the input string.
   • Other variables: O(1)
     • The space occupied by other variables such as n, k, and num is constant.

   Thus, the overall space complexity is O(n) due to the space occupied by the stack.

In summary, the time complexity of the code is O(n), and the space complexity is O(n).