리트코드 - 394. Decode String

스택을 초기화한다.
각 문자를 반복한다.

• 숫자인 경우: 숫자가 두 자리 이상일 수도 있기 때문에, '['가 나올 때까지 전체 숫자를 추적한다.
• '['인 경우 : 현재까지의 완성된 문자열과 반복할 숫자를 stk에 저장한다.
• ']'인 경우:  스택을 pop한다. 그러면 현재까지 완성된 문자열과 반복할 숫자가 반환될 것이다. 그러면 반복할 숫자에 현재 문자열을 곱하고 완성된 문자열 뒤에 붙여준다. 
• 문자열일 경우 : 현재 문자열에 추가한다.

class Solution:
    def decodeString(self, s: str) -> str:
        stk = []
        num = 0
        current_str = ""
        for c in s: # O(n)
            if c.isdigit(): # O(1) 실제로 isdigit의 시간복잡도는 O(n)이지만, 해당 풀이에서는 하나의 문자만 받는 것이 보장되기 때문.
                num = num * 10 + int(c) # O(1)
            elif c == "[": # O(1)
                stk.append((current_str, num)) # O(1)
                current_str, num = "", 0 # O(1)
            elif c == "]": # O(1)
                last_word, tmp_num = stk.pop() # O(1)
                current_str = last_word + current_str * tmp_num # O(1)
            else:
                current_str += c # O(1)
        return current_str

 

시간 복잡도 : 주어진 입력 문자열 s를 한 번씩 순회하므로 시간 복잡도는 O(n)이다. 이때 반복문에서 isdigit 메서드를 호출하는데 isdigit은 정수여부를 판단하기 위해 문자열을 모두 순회하므로 O(n)의 시간복잡도를 가지지만, 해당 반복문에서는 이미 문자열을 하나씩 순회하는 조건이기 때문에 실질적으로 O(1)의 시간복잡도를 가지게 된다.

 

공간 복잡도 : 스택 배열과 문자열을 저장하기 위한 변수를 할당하므로 공간복잡도는 O(n)이다.