[LeetCode] 2375. Construct Smallest Number From DI String (Python)

Problem

 

Solution

stack
brute force

I 가 나오면 숫자 증가,D 가 나오면 숫자가 감소하도록하여 가장 작은 수를 반환하는 문제.

지난번 비슷한 문제에서 dfs 를 사용했어서 비슷하게 풀면되는 줄 알고 삽질함

 

사전적으로 가장 작은 숫자를 반환해야하므로 가장 작은 수인 1부터 숫자 추가.

마지막 인덱스이거나 patter[i] == I 이면 stack 모두 비울때까지 res 배열에 넣는다. stack 이라서 FIFO 구조로 먼저 넣은 숫자 먼저 res에 저장된다.

 

마지막에 res 배열에 있는 숫자들 join 해주면됨!

 

pattern의 길이가 8까지라서 hint에도 bruteforce로 다해보라고 권했음.

 

 

Code

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        res = []
        stack = []
        n = len(pattern)

        for i in range(n+1):
            stack.append(str(i+1)) #start with 1
            #last index or patter[i] = I, popup stack
            if i == n or pattern[i] == 'I':
                while stack:
                    res.append(stack.pop())
        return ''.join(res)

 

Complexity

Time Complexity

loop를 n번만큼 순회한다. -> O(N)

 

Space Complexity

추가적인 리스트 사용 -> O(N)