[LeetCode 75] Medium - 394. Decode String ★★★

394. Decode String

 

"Decode String" 문제는 **스택(stack)**을 이용한 문자열 복호화 문제입니다.

---

🧾 문제 요약

• 입력 문자열 s는 인코딩된 문자열입니다.
• 인코딩 형식은: k[내용] (내용을 k번 반복)
• 중첩(nested) 구조도 허용됩니다. 예: "3[a2[c]]" → "accaccacc"
• 문자열을 디코딩하여 반환해야 합니다.

✅ 풀이 전략: 스택 사용

중첩 구조 때문에 재귀나 스택이 필요합니다. 여기서는 스택 기반 풀이를 소개합니다.

---

✅ Python 코드

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        current_num = 0
        current_str = ""

        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)  # 두 자리 이상 숫자도 처리
            elif char == '[':
                stack.append((current_str, current_num))  # 현재 상태 저장
                current_str = ""
                current_num = 0
            elif char == ']':
                prev_str, num = stack.pop()
                current_str = prev_str + current_str * num  # 복원
            else:
                current_str += char  # 일반 문자

        return current_str

 

🔍 핵심 흐름 설명

숫자	반복 횟수 저장 (ex: 12[a])
[	스택에 현재 문자열과 반복 수 저장
]	스택에서 꺼내 반복 적용
문자	현재 문자열에 추가

 

---

⏱ 시간복잡도

• 최악의 경우: O(N) (모든 문자 1번씩 처리)
• 공간복잡도: O(N) (중첩된 스택 저장)

---

🎯 요약

중첩 처리	스택 활용 ((이전문자열, 반복수) 저장)
숫자 처리	두 자릿수 이상도 고려 num = num * 10 + int(char)
재귀 가능	재귀 DFS로도 구현 가능하지만 스택이 더 직관적

 

 

class Solution:
    def decodeString(self, s: str) -> str:
        dictionary = {']':'['}
        stack = []

        for w in s:
            if w != ']':
                stack.append(w)
            else:
                sub = ''
                while stack[-1] != '[':
                    sub = stack.pop() + sub # 왼쪽으로 string 추가해야하므로
                stack.pop()
            
                num_str = ''
                while stack and stack[-1].isdigit():
                    num_str = stack.pop() + num_str # 왼쪽으로 string 추가해야하므로
                stack.append(int(num_str)*sub)

        return ''.join(stack)