Decode String

Q: 두 자리 이상의 개수는 어떻게 처리하나요?

읽으면서 숫자를 만드세요. 0에서 시작해 각 숫자에 대해 count = count × 10 + digit 으로 설정합니다. [ 가 나오면 숫자가 완성되므로 300[a] 는 300을 나타냅니다. 숫자를 푸시하자마자 count를 0으로 초기화하세요. 그렇지 않으면 다음 그룹의 숫자가 여기에 더해집니다.

Q: 스택은 왜 각 괄호 앞에 나온 텍스트를 저장할까요?

[ 가 나오면 해당 수준에서 지금까지 디코딩한 텍스트는 아직 완성되지 않았습니다. 그룹의 복사본이 그 뒤에 와야 하기 때문입니다. 이를 스택에 넣어 안전하게 보관한 다음 빈 문자열에서 본문을 디코딩합니다. 짝이 맞는 ] 가 나오면 스택에서 꺼내 해당 텍스트를 되찾고 복사본을 그 뒤에 추가합니다.

보통스택 재귀

+10

인코딩된 문자열은 반복되는 텍스트를 k[text]로 나타내며, 이는 text가 연속해서 k번 쓰인다는 뜻입니다. 그룹은 다른 그룹 안에 들어갈 수 있으므로 2[a3[b]]는 abbbabbb를 나타냅니다. 인코딩된 문자열 s를 받아 디코딩된 문자열을 반환하는 함수를 작성하세요.

모든 대괄호 바깥에 있는 문자는 그대로 유지됩니다. 각 반복 횟수는 양의 정수이며 해당 [ 바로 앞에 쓰이고, 숫자는 그 외에는 나타나지 않습니다.

함수

decodeString(s: string) → string

sstring: 인코딩된 문자열
반환값string: 디코딩된 문자열

제약 조건

1 ≤ s.length ≤ 10⁴
s에는 소문자 영어 문자, 숫자, [ 및 ]만 포함되어 있습니다.
s는 유효한 인코딩입니다. 모든 [ 뒤에는 개수가 오고 이에 대응하는 ]가 있으며, 비어 있는 대괄호는 없습니다.
모든 개수 k는 1 ≤ k ≤ 300을 만족하며 앞에 0이 오지 않습니다.
괄호는 최대 100단계까지 중첩될 수 있습니다.
디코딩된 문자열의 길이는 최대 5 × 10⁴자입니다.

예제

입력: s = "2[ab]3[c]x"
출력: "ababcccx"
설명: 2[ab]는 abab를 만들고 3[c]는 ccc를 만듭니다. x는 모든 괄호 바깥에 있으므로 그대로 복사되어 ababcccx가 됩니다.

입력: s = "2[x3[yz]]"
출력: "xyzyzyzxyzyzyz"
설명: 먼저 안쪽을 해독하세요: 3[yz]는 yzyzyz이므로 바깥 그룹의 본문은 xyzyzyz입니다. 두 번 쓰면 xyzyzyzxyzyzyz입니다.

입력: s = "q10[w]e"
출력: "qwwwwwwwwwwe"
설명: 개수는 두 자리 숫자로 읽은 10이므로 q와 e 사이에 w가 열 번 나타납니다. [ 옆의 숫자만 읽는 코드는 0번 반복합니다.

제출 시 숨은 테스트 +22개

후속 질문

디코딩된 문자열은 입력보다 훨씬 길 수 있습니다. 디코딩된 길이가 10^18에 이를 수 있을 때, 디코딩된 문자열을 만들지 않고 위치 i의 문자만 반환하려면 어떻게 해야 할까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

개수는 괄호 앞에 오지만, 괄호 안에 무엇이 있는지 알아야 복사본을 쓸 수 있고, 괄호 안에는 더 많은 그룹이 들어갈 수 있습니다. 따라서 그룹 안의 모든 그룹이 끝난 뒤에야 그 그룹을 확장할 수 있습니다. 아래의 각 방법은 가장 안쪽 그룹부터 처리하는 방법입니다. 문자열을 안쪽에서 바깥쪽으로 다시 쓰거나, 재귀 호출이 바깥쪽 그룹보다 먼저 안쪽 그룹을 처리하게 하거나, 아직 끝나지 않은 바깥쪽 그룹을 스택에 보관하면 됩니다. 아래에서 n은 입력의 길이, m은 디코딩된 문자열의 길이, d는 가장 깊은 중첩 깊이입니다.

가장 안쪽 그룹을 확장한 다음 반복하세요

핵심 아이디어

종이에 직접 쓰면서 푸는 것처럼 문자열을 해독하세요. 내부에 다른 그룹이 없는 그룹을 찾아 그 자리에 내용을 반복해 써 넣고, 다시 살펴보세요. 2[x3[yz]]에서 3[yz] 그룹은 내부에 아무것도 없으므로 문자열은 2[xyzyzyz]가 되고, 한 번 더 확장하면 답을 얻습니다.

문자열에서 첫 번째 ]는 항상 이런 그룹을 닫습니다. 그 전에 닫힌 다른 그룹은 없으므로, 이 괄호와 그에 대응하는 [ 사이에는 대괄호가 있을 수 없습니다. 해당 [는 왼쪽에 있는 가장 가까운 대괄호이고, 반복 횟수는 바로 앞에 이어진 숫자들입니다. 반복 횟수와 대괄호, 본문을 본문을 k번 쓴 문자열로 바꾸고, ]가 더 이상 남지 않을 때까지 반복하세요.

이 방법은 올바르지만, 확장할 때마다 문자열 전체를 다시 만듭니다. 그룹이 b개이고 문자열 길이가 m자까지 늘어난다면 문자를 최대 b × m번 복사하게 됩니다. 그룹이 나란히 약 1,300개 있는 숨겨진 테스트에서는 27,688자를 만드는 데 약 2,500만 번의 복사가 발생합니다. 입력을 한 번 훑기만 하면 되는 작업인데도 말입니다.

알고리즘

문자열에서 첫 번째 ]를 찾습니다. 없으면 문자열은 디코딩된 것이므로 반환합니다.
가장 가까운 [를 찾을 때까지 왼쪽으로 이동합니다. 두 괄호 사이의 텍스트가 그룹의 본문입니다.
해당 [ 앞에 있는 숫자들을 지나 더 왼쪽으로 이동하여 반복 횟수 k로 읽습니다.
첫 번째 숫자부터 ]까지의 모든 내용을 본문을 k번 쓴 것으로 바꿉니다.
1단계로 돌아갑니다.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

재귀 하강

핵심 아이디어

형식은 재귀적입니다. 인코딩된 문자열은 문자와 그룹의 연속이며, 그룹의 본문도 다시 인코딩된 문자열입니다. 따라서 공유 위치에서 해당 수준을 끝내는 ] 또는 입력의 끝에 도달할 때까지 읽고, 읽은 내용을 디코딩하여 반환하는 함수 하나, decode를 작성하세요.

decode가 숫자를 만나면 전체 숫자를 읽고 [를 건너뛴 다음 본문을 디코딩하기 위해 자기 자신을 호출합니다. 더 깊은 호출에서 더 안쪽의 ]를 이미 소비했으므로, 이 호출은 짝이 맞는 ]에서 멈춥니다. 호출한 쪽은 ]를 건너뛰고 본문을 k번 추가한 다음 계속 읽습니다. 2[x3[yz]]의 경우, 바깥쪽 호출은 2를 읽고, 다음 호출은 x와 3을 읽습니다. 세 번째 호출은 yz를 반환하고, 중간 호출은 xyzyzyz를 반환하며, 바깥쪽 호출은 이를 두 번 씁니다.

입력 문자는 각각 한 번씩 읽습니다. 실제 비용은 복사에 있습니다. 출력 문자는 자신을 둘러싼 각 그룹마다 한 번씩 복사되므로, 시간 복잡도는 중첩 깊이 d에 대해 O(n + m·d)입니다. 재귀 호출도 d단계 깊이까지 이어집니다. 깊이가 100단계인 경우는 괜찮지만, 입력이 매우 깊게 중첩되면 호출 스택이 넘칠 수 있습니다. 예를 들어 Python은 기본적으로 중첩 호출이 1,000회에 도달하면 중단합니다.

알고리즘

모든 호출이 공유하는 위치 pos 하나를 유지하며, 첫 번째 문자에서 시작합니다.
decode()는 pos가 문자열 안에 있고 ] 위에 있지 않은 동안 반복합니다.
문자라면 해당 문자를 추가하고 다음으로 이동합니다.
숫자라면 전체 숫자 k를 읽고, [를 건너뛰고, 본문에 대해 decode()를 호출하고, ]를 건너뛴 다음, 본문을 k번 추가합니다.
만들어진 내용을 반환합니다. 첫 번째 호출은 디코딩된 문자열을 반환합니다.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

스택을 사용한 한 번의 순회

핵심 아이디어

재귀에서는 열린 각 그룹마다 미완성 텍스트 조각 하나를 호출 프레임 안에 유지합니다. 대신 그 조각들을 직접 만든 스택에 보관하고 문자열을 한 번의 루프로 읽을 수 있습니다.

현재 레벨에서 두 가지를 추적합니다. 지금까지 디코딩한 텍스트인 current와 읽고 있는 숫자인 count입니다. 숫자가 나오면 count를 count × 10 + digit으로 늘리므로 10과 300을 올바르게 처리할 수 있습니다. [는 레벨을 엽니다. current와 count를 스택에 넣은 다음 둘 다 초기화합니다. 문자는 current에 추가합니다. ]는 레벨을 닫습니다. 저장된 텍스트와 카운트를 꺼내고, current는 저장된 텍스트 뒤에 current를 count번 반복한 결과가 됩니다.

2[x3[yz]]를 따라가 봅시다. 첫 번째 [에서 (빈 값, 2)를 스택에 넣습니다. x가 current를 x로 만듭니다. 두 번째 [에서 (x, 3)을 스택에 넣고, 새로 시작한 current에 yz가 채워집니다. 첫 번째 ]에서 (x, 3)을 꺼내므로 current는 xyzyzyz가 됩니다. 마지막 ]에서 (빈 값, 2)를 꺼내고, current는 xyzyzyzxyzyzyz가 됩니다.

그룹은 열린 순서의 역순으로 닫히므로, 스택의 맨 위는 항상 ]가 돌아갈 레벨입니다. 작업량은 재귀 방식과 동일한 O(n + m·d)이지만, 깊게 중첩되어도 리스트만 커질 뿐 호출 스택은 커지지 않습니다.

알고리즘

빈 스택, 빈 current, count = 0으로 시작합니다.
숫자를 만나면 count = count × 10 + digit으로 설정합니다.
[를 만나면 쌍(current, count)을 푸시한 다음, current를 빈 값으로, count를 0으로 재설정합니다.
문자를 만나면 current에 추가합니다.
]를 만나면 (before, k)를 팝하고, current를 before 뒤에 current를 k번 반복한 값으로 설정합니다.
마지막 문자까지 처리한 후 current를 반환합니다.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

함정과 경계 사례

대부분의 오답은 개수를 잘못 읽거나 저장된 텍스트가 들어갈 위치를 잘못 파악해서 생깁니다.

한 자릿수만 전체 개수로 읽기. q10[w]e에서 개수는 10입니다. [ 앞의 숫자만 가져오는 코드는 w를 0번 반복합니다.
count를 스택에 넣은 뒤 0으로 초기화하는 것을 잊기. 그러면 다음 그룹의 숫자가 이전 숫자에 더해져서 2[a3[b]]의 내부 개수를 23으로 읽게 됩니다.
저장된 텍스트 앞에 복사본을 넣기. ]를 만나면 결과는 그룹 앞의 텍스트 다음에 복사본이 오는 형태이므로, ab2[c]는 ccab가 아니라 abcc입니다.
최상위 수준의 글자를 놓치기. 2[ab]3[c]x의 x는 어떤 괄호 안에도 없지만 여전히 정답에 포함되어야 합니다.
긴 불변 문자열에 문자를 하나씩 추가하기. 추가할 때마다 문자열 전체가 복사될 수 있으며, 이로 인해 50,000자짜리 정답을 만드는 데 수십억 번의 복사가 발생할 수 있습니다. 조각을 리스트나 문자열 빌더에 모으세요.

자주 묻는 질문4

Decode String의 시간 복잡도는 무엇인가요?

입력을 읽는 데는 O(n)이 걸립니다. 출력을 만드는 과정에서는 각 문자가 자신이 속한 그룹마다 한 번씩 복사되므로, 총 시간은 O(n + m·d)입니다. 여기서 m은 디코딩된 길이이고 d는 중첩 깊이입니다. 모든 개수가 최소 2이면 각 그룹은 이를 둘러싼 그룹의 길이의 최대 절반이므로, 복사 횟수는 2m 미만입니다. 답 자체가 m개의 문자를 가지므로 어떤 방법도 O(m)보다 빠를 수 없습니다.

Decode String를 재귀로 풀어야 할까요, 아니면 스택으로 풀어야 할까요?

둘 다 같은 작업을 합니다. 재귀는 그룹의 본문 자체가 인코딩된 문자열이므로 형식을 직접 따르며, 면접에서 작성하기 가장 빠른 방법인 경우가 많습니다. 스택 버전은 하나의 루프에서 같은 작업을 수행하고 완료되지 않은 바깥쪽 단계들을 목록에 보관하므로, 중첩이 매우 깊어도 호출 스택이 넘치지 않습니다. 면접관이 수천 단계 깊이로 중첩된 입력에 대해 묻는다면 스택이 답입니다.

두 자리 이상의 개수는 어떻게 처리하나요?

읽으면서 숫자를 만드세요. 0에서 시작해 각 숫자에 대해 count = count × 10 + digit으로 설정합니다. [가 나오면 숫자가 완성되므로 300[a]는 300을 나타냅니다. 숫자를 푸시하자마자 count를 0으로 초기화하세요. 그렇지 않으면 다음 그룹의 숫자가 여기에 더해집니다.

스택은 왜 각 괄호 앞에 나온 텍스트를 저장할까요?

[가 나오면 해당 수준에서 지금까지 디코딩한 텍스트는 아직 완성되지 않았습니다. 그룹의 복사본이 그 뒤에 와야 하기 때문입니다. 이를 스택에 넣어 안전하게 보관한 다음 빈 문자열에서 본문을 디코딩합니다. 짝이 맞는 ]가 나오면 스택에서 꺼내 해당 텍스트를 되찾고 복사본을 그 뒤에 추가합니다.

Python

def decodeString(s):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "2[ab]3[c]x"

기대값

"ababcccx"

Decode String

함수

제약 조건

예제

힌트

풀이

가장 안쪽 그룹을 확장한 다음 반복하세요

재귀 하강

스택을 사용한 한 번의 순회

함정과 경계 사례

자주 묻는 질문4

비슷한 문제