394. Decode String

Decode String - LeetCode

1. Stack과 Dict을 이용한 풀이

from collections import deque


class Solution:
    def decodeString(self, s: str) -> str:
        list1 = deque(list(s))
        stack = []
        dict1 = {}
        dict_key = 65
        while list1:
            cur = list1.popleft()
            if cur != "]":
                stack.append(cur)
            else:
                temp = []
                while stack and stack[-1] != "[":
                    t = stack.pop()
                    if t in dict1:
                        temp.append(dict1[t])
                    else:
                        temp.append(t)
                stack.pop()
                temp = temp[::-1]
                temp2 = []
                while stack and stack[-1].isdigit():
                    temp2.append(stack.pop())
                temp2 = temp2[::-1]
                target_num, target_str = int("".join(temp2)), "".join(temp)
                dict1[chr(dict_key)] = target_str * target_num
                stack.append(chr(dict_key))
                dict_key += 1
        result = ""
        for string in stack:
            if string in dict1:
                result += dict1[string]
            else:
                result += string
        return result

 

주어지는 문자열은 소문자, 여는 괄호, 닫는 괄호, 숫자로만 구성되어있다고 조건에서 설명하고 있다.

1. 괄호를 닫는 순간 그 안의 문자들로 문자열을 만든다.

1.1. 만일 그 안의 문자가 Dict의 Key로 존재한다면 해당 Key가 가지고 있는 문자열을 불러낸다.

2. 괄호 바깥의 숫자 문자열을 조합해 반복 횟수를 구한다.

2. 그리고 구한 문자열 * 반복 횟수의 결과 문자열을 만들고, 그 문자열을 Dict에 저장한다. 

 

위 과정을 기존 문자열을 전부 순회할 때까지 반복한 뒤 스택에 남아있는 문자들을 조합해 결과를 반환한다.

이 때도 1.1에 기술한 조건을 적용한다.

 

반드시 생각이 끝난 뒤에 코딩에 들어갈 것.