394. Decode String

Published at 2026-11-11

https://leetcode.com/problems/decode-string/description/

문제 요약: 주어진 문자열 s을 다음 과정대로 디코딩한다.

k[문자열] ← 형태인 문자열이 있을때, [] 안의 문자열을 k번 반복한 원래 문자열을 반환.
괄호는 중첩될 수 있다.

풀이

직관

여는 괄호를 만났을 때,
1. 바로 앞에 있었던 숫자를 알고 있어야 한다.
2. 닫는 괄호를 만날때까지 만나는 문자를 기록해둔다.
닫는 괄호를 만나면, 저장한 문자열과 저장한 숫자를 사용해 디코딩된 문자열을 만들어 결과에 이어 붙인다.

풀이 과정

일단 문자열의 케이스를 다음과 같이 4가지 경우로 나눠서 처리해야 했다: 여는 괄호, 닫는 괄호, 숫자, 알파벳문자
숫자는 반복 횟수에만 쓰이기 때문에, 숫자를 만나면 일단 여는 괄호를 만날때까지 기록한다.(숫자는 일의 단위 이상일수도 있기 때문에 계속 기록 필요)
문자를 만난 경우도, 반복해야하는 끝 문자를 모르기 때문에 일단 계속 기록해둔다.
여는 괄호를 만났을때, 기록중이었던 문자열과, 반복할 횟수를 잠시 치워두기 위해 튜플형태로 스택에 넣는다. (튜플은 아니어도되지만, 순서가 헷갈려질수있어서 튜플 형태로 같이 저장)
4에서 스택에 쌓았다면, 작업하려고 기록중이었던 숫자와 문자 변수는 새로운 기록을 위해 초기화한다.
닫는 괄호를 만났다면, 4에서 스택에 저장했던 반복횟수만큼 현재 쌓고있던 문자를 반복해야 한다.
그리고 4에서 스택에 반복횟수랑 같이 저장했던 문자열은, 현재 기록하고있던, 6에서 반복시킨 문자열의 앞에 위치해야 한다.
7의 과정까지 했다면, 새로 만들어진 디코딩 문자열은 다시 작업중인 내 손으로 갖고오기위해 기록용 문자열 변수 공간에 새로 갈아끼워넣는다.

class Solution:
    # - 숫자는 숫자 임시 저장, 문자는 문자대로 임시 저장한다.
    #   (아직 어느 범위까지 작업할지 모르기 때문. 우선 작업 공간?에 두는것이다)
    # - 여는 괄호를 만나면, 작업중이던(알아내고 있던) 문자나 횟수를 일단 임시 저장해둔다.
    # - 닫는 괄호를 만나면, 지난 작업을 꺼내서 참고하여 하던 작업을 마무리한다.
    def decodeString(self, s: str) -> str:
        curr_str = ''  # 현재 작업중인 문자열(=찾는중인, 반복할 대상을 저장한다)
        curr_cnt = ''  # 현재 작업중인 숫자(=알아내가고 있는 반복횟수)
        stack = []  # 튜플형태로 저장. ({현재 작업중이던 문자}, {현재 작업중이던 횟수})

        for ss in s:
            if ss == '[':
                stack.append((curr_str, int(curr_cnt)))
                curr_str = ''
                curr_cnt = ''
            elif ss == ']':
                str_pop, cnt_pop = stack.pop()
                curr_str = str_pop + (curr_str * cnt_pop)
            elif ss.isdigit():
                curr_cnt += ss
            else:
                curr_str += ss

        return curr_str

시간복잡도: O