•
문제 링크 : 
LeetCodeDecode String - LeetCode
•
문제 설명 : 제공된 압축 문자열을 평문 문자열로 변환하는 문제이다.
•
풀이 방법
◦
우선 []가 중첩으로 보고 재귀를 생각해야한다.
▪
그래서 우선 중첩이 없는 문자열을 먼저 처리하도록 구현한 후 재귀를 넣었다.
▪
처리된 문자는 바로 문자열로 안더하고, stack에 넣어서 최종적으로 괄호가 없는 스택이 완성되면 join 으로 합쳐주었다.
•
시간복잡도 :
•
성공 코드
class Solution:
def decodeString(self, s: str) -> str:
stack = []
num_set = {str(num) for num in range(10)}
temp = ""
for ch in s:
if ch == ']':
# [] 사이에 들어가는 압축 문자 구하기
while stack:
pop_ch = stack.pop()
if pop_ch == '[':
break
temp = pop_ch + temp
# [] 사이 압축 문자 반복 횟수 구하기
count = ""
while stack:
if stack[-1] not in num_set:
break
count = stack.pop() + count
# [] 괄호 사이에 존재하는 문자열을 재귀 처리
stack.append(int(count) * self.decodeString(temp))
temp = ""
else:
stack.append(ch)
return "".join(stack)
Python
복사