Decode Ways

Q: Decode Ways의 시간 복잡도는 얼마인가요?

상향식 해법은 각 숫자를 한 번씩 읽고 일정한 작업을 수행하므로, O(n) 시간과 O(1) 추가 공간을 사용합니다. 메모이제이션을 적용한 재귀도 O(n) 시간이 걸리지만, 메모와 호출 스택에 O(n) 공간을 사용합니다. 일반 재귀는 지수 시간입니다. 1로만 이루어진 문자열에서는 호출 횟수가 1.618^n 처럼 증가합니다.

Q: Decode Ways에서 0은 어떻게 처리하나요?

0 은 단독으로 문자가 될 수 없으므로 앞에 있는 숫자와 짝을 이루어야 하며, 10 과 20 만 코드입니다. 상향식 반복문에서는 한 자리 숫자의 경우 0 은 아무것도 더하지 않고, 1 또는 2 뒤에 오는 경우에만 두 자리 앞의 개수를 더합니다. 맨 앞에 0 이 있거나, 0이 연속으로 두 개 있거나, 3부터 9까지의 숫자 뒤에 0 이 오면 답은 0이 됩니다.

보통동적 계획법

+10

대문자로 이루어진 메시지를 A = 1, B = 2 등 Z = 26까지의 코드로 숫자로 바꾸고, 구분자 없이 코드를 차례로 이어 붙였습니다. 숫자 문자열 s가 주어집니다. 이 문자열을 만들 수 있는 서로 다른 메시지의 수를 반환하세요.

각 문자는 한 자리 숫자 또는 서로 이웃한 두 자리 숫자로 읽으며, 코드는 0으로 시작하지 않습니다. 06은 6이 아니며, 0만으로는 문자를 나타낼 수 없습니다. 읽을 수 있는 방법이 없다면 0을 반환하세요.

함수

numDecodings(s: string) → integer

sstring: 디코딩할 숫자 문자열
반환값integer: s로 인코딩되는 문자 메시지의 수

제약 조건

1 ≤ s.length ≤ 100
s에는 0부터 9까지의 숫자만 들어 있으며, 0으로 시작할 수도 있습니다.
모든 접두사와 접미사 s의 판독값은 2³¹개보다 적으므로, 답과 계산 과정에서 구하는 모든 개수는 부호 있는 32비트 정수에 들어갑니다.

예제

입력: s = "2611"
출력: 4
설명: 네 가지 해석은 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK), 26 11 (ZK)입니다. 61은 26보다 크므로 가운데 숫자들은 절대 짝을 이루지 않습니다.

입력: s = "1203"
출력: 1
설명: 0은 앞에 있는 2와 짝을 이루어 20이 되어야 하며, 이로 인해 1 20 3(ATC)으로 읽게 됩니다. 먼저 12로 읽으면 0이 홀로 남고, 03은 0으로 시작합니다.

입력: s = "06"
출력: 0
설명: 첫 번째 문자는 0으로 시작해야 합니다. 0 하나만으로는 문자가 아니고 06은 코드가 아니므로, 어떤 메시지도 이 문자열을 생성하지 않습니다.

제출 시 숨은 테스트 +25개

후속 질문

s에 1부터 9까지의 숫자 중 하나를 의미하는 *도 들어갈 수 있다면 어떨까요? O(n) 시간에 해석 가능한 경우의 수를 세고, 그 수를 10^9+7로 나눈 나머지를 반환할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

각 숫자는 그 자체로 하나의 문자이거나 이웃한 숫자와 합쳐져 두 자리 문자가 되므로, 해석의 수는 피보나치 수처럼 늘어납니다. 숫자 1이 45개만 있어도 해석은 이미 1836311903가지입니다. 해석을 모두 나열하는 것은 불가능합니다. 문제를 해결하는 핵심은 해석을 끝내는 방법의 수가 도달한 위치에만 달려 있으므로 각 위치를 한 번씩만 세면 된다는 점입니다. 주의해야 할 부분은 0입니다. 0은 10 또는 20의 두 번째 숫자일 때만 올 수 있습니다.

재귀를 사용해 두 가지 읽기를 모두 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

i 인덱스에 서서 다음 숫자를 살펴보세요. 숫자가 0이면 여기서 시작하는 글자는 없으며 이 경로에서는 해석 결과가 나오지 않습니다. 그렇지 않으면 해당 숫자를 글자 하나로 읽고 i+1부터 나머지의 해석 결과 개수를 셀 수 있습니다. 그 숫자와 다음 숫자를 합쳐 10부터 26까지의 수가 되면, 둘을 글자 하나로 읽고 i+2부터 셀 수도 있습니다. 두 선택지는 서로 다른 첫 글자를 만들므로, 중복 없이 개수를 더하면 됩니다. i가 문자열의 끝에 도달하면 하나의 해석을 완성한 것이므로 1을 반환합니다.

"2611"의 경우 첫 글자는 2 또는 26입니다. 2를 선택하면 61은 너무 크기 때문에 다음 글자는 6이어야 합니다. 그러면 두 분기 모두 마지막에 1 1 또는 11로 끝나므로 전체 개수는 2 × 2 = 4입니다.

답은 맞지만 아무것도 기억하지 않습니다. 1로만 이루어진 문자열에서는 호출마다 두 갈래로 나뉘고 호출 횟수가 피보나치 규칙을 따르므로, 1이 45개면 호출이 약 5 × 10^9번 발생합니다. 작업량은 답의 크기에 따라 줄어들지도 않습니다. 1이 44개 나오고 그 뒤에 3이 55개, 마지막에 0이 오는 경우 답은 0이지만, 각 경로가 마지막 숫자에서 끝나기 전까지 재귀 호출은 3이 이어지는 부분 전체를 통과하면서 1로 이루어진 모든 해석을 살펴봅니다. 호출 횟수는 약 10^11번입니다.

알고리즘

인덱스 i부터 끝까지 숫자를 읽는 방법의 수를 세는 도우미 waysFrom(i)를 작성하세요.
i가 s의 길이와 같으면 1을 반환하세요.
i의 숫자가 0이면 0을 반환하세요.
다음 문자가 숫자 하나를 차지하는 읽기 방법인 waysFrom(i+1)에서 시작하세요.
숫자 i와 i+1이 26 이하의 수를 이루면 waysFrom(i+2)를 더하세요. waysFrom(0)을 반환하세요.

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

메모를 사용한 재귀

핵심 아이디어

재귀는 같은 질문을 계속 반복합니다. "11111"에서는 인덱스 3부터의 개수가 1 1 1 뒤에도, 11 1 뒤에도, 1 11 뒤에도 필요하며, 인덱스 3 이후의 숫자에만 의존하기 때문에 매번 같은 결과가 나옵니다. 처음 계산할 때 각 개수를 배열 memo에 저장하고, 그다음부터는 거기서 읽어 오세요.

아직 계산하지 않은 슬롯은 0이 아니라 -1로 표시하세요. 여기서 0은 실제 답입니다. 30으로 끝나는 문자열에서는 모든 위치의 읽기 횟수가 0입니다. 표시값으로 0을 사용하면 방문할 때마다 해당 위치를 미지 상태로 보고, 재귀는 이전처럼 느려집니다.

위치는 n개이고 각 위치는 상수 시간의 작업으로 한 번씩 계산되므로, 시간 복잡도는 O(n)입니다. 메모와 호출 스택은 각각 O(n)의 공간을 사용합니다. 여기서는 호출이 최대 100단계까지 중첩되며, 모든 언어가 이를 처리할 수 있습니다.

알고리즘

인덱스마다 하나의 슬롯이 있는 배열 memo를 만들고, 모든 값을 -1로 설정합니다.
waysFrom(i)에서 문자열의 끝에 도달하면 1을 반환하고, -1이 아니면 memo[i]를 반환합니다.
그렇지 않으면 단순 재귀와 같이 계산합니다. 0이면 0을 반환하고, 그렇지 않으면 두 자릿수가 10에서 26을 이루는 경우 waysFrom(i+1)에 waysFrom(i+2)를 더합니다.
0도 포함해 계산한 값을 memo[i]에 저장하고 반환합니다.
waysFrom(0)을 반환합니다.

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

두 개의 카운터를 사용한 상향식

핵심 아이디어

재귀를 뒤집어 접두사의 개수를 세어 보세요. ways(i)를 처음 i개 숫자를 읽는 방법의 수라고 합시다. 이러한 읽기에서 마지막 글자는 단독으로 쓰인 인덱스 i-1의 숫자일 수도 있습니다. 이 경우 숫자는 1부터 9까지여야 하며, 나머지를 읽는 방법은 ways(i-1)개입니다. 또는 인덱스 i-2와 i-1의 두 숫자일 수도 있습니다. 이 경우 두 숫자는 10부터 26까지의 수를 이루어야 하며, 나머지를 읽는 방법은 ways(i-2)개입니다. 따라서 ways(i)는 조건을 만족하는 경우의 수를 더한 값입니다. 빈 접두사는 빈 메시지라는 한 가지 읽기 방법이 있으므로 ways(0) = 1입니다.

"1203"을 따라가 보세요. 1 뒤의 개수는 1입니다. 12 뒤에는 1 2와 12, 두 가지이므로 개수는 2입니다. 0은 단독으로 쓸 수 없고 20만 유효하므로, 개수는 2 앞의 개수인 1로 돌아갑니다. 3은 단독으로 쓸 수 있고 03은 코드가 아니므로, 개수는 1로 유지됩니다.

각 개수는 두 단계 전의 개수까지만 살펴보므로, 표 대신 twoBack과 oneBack 두 변수를 사용합니다. 숫자마다 일정한 작업을 수행하며 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)이고 재귀는 전혀 사용하지 않습니다.

알고리즘

twoBack = 0과 oneBack = 1을 빈 접두사의 개수로 설정합니다.
각 인덱스 i에 대해 current를 0으로 시작하고, 숫자 i가 0이 아니면 oneBack을 더합니다.
i ≥ 1이고 숫자 i-1이 0이 아니며, 숫자 i-1과 i가 26 이하의 수를 이루면 twoBack을 더합니다.
값을 한 칸씩 이동합니다. twoBack = oneBack으로 설정한 다음 oneBack = current로 설정합니다.
마지막 숫자까지 처리한 후 oneBack을 반환합니다.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

함정과 경계 사례

이 문제에서 거의 모든 오답은 0을 잘못 처리하거나, 계산한 결과를 잊어버리는 메모에서 비롯됩니다.

0을 글자로 취급하거나 06을 6으로 취급하는 경우입니다. 0은 10 또는 20의 끝자리로만 올 수 있으므로 "30", "100", "06"은 모두 해석 방법이 0개입니다.
두 자리 숫자 조각을 ≤ 26인지 여부만 확인하는 경우입니다. 숫자로는 05가 5이지만, 코드로는 사용할 수 없습니다. 두 자리 숫자의 첫 번째 숫자가 0이 아닌지 확인하세요.
아직 계산하지 않은 메모 칸의 표시로 0을 사용하는 경우입니다. 실제로 해석 방법이 0개인 위치가 많으므로, 해당 칸은 저장된 것으로 간주되지 않아 방문할 때마다 다시 계산됩니다. 1이 44개 이어지고 그 뒤에 3들이 오며 마지막에 0이 오는 경우, 모든 칸의 값은 0이 되어 호출 횟수는 다시 약 10^11회에 이릅니다.
인덱스 0 앞의 숫자를 읽는 경우입니다. 두 자리 숫자 확인은 i ≥ 1일 때만 하세요. Python에서는 s[-1]이 마지막 숫자를 조용히 읽고, 다른 언어에서는 문자열 범위 밖을 읽습니다.
s를 하나의 숫자로 변환하는 경우입니다. 자릿수가 100개인 수는 어떤 정수형에도 들어가지 않으며, 변환 과정에서 정답을 바꾸는 선행 0도 사라집니다. 숫자를 하나씩 처리하세요.
Lua와 R에서는 위치가 1부터 시작하므로 문자열의 끝은 위치 n+1이고, 첫 번째 두 자리 숫자 확인은 위치 2에서 합니다.

자주 묻는 질문4

Decode Ways의 시간 복잡도는 얼마인가요?

상향식 해법은 각 숫자를 한 번씩 읽고 일정한 작업을 수행하므로, O(n) 시간과 O(1) 추가 공간을 사용합니다. 메모이제이션을 적용한 재귀도 O(n) 시간이 걸리지만, 메모와 호출 스택에 O(n) 공간을 사용합니다. 일반 재귀는 지수 시간입니다. 1로만 이루어진 문자열에서는 호출 횟수가 1.618^n처럼 증가합니다.

Decode Ways는 Climbing Stairs와 어떤 관련이 있나요?

둘 다 크기가 1과 2인 단계로 선을 덮는 방법의 수를 셉니다. Climbing Stairs에서는 모든 단계가 허용되므로 경우의 수는 피보나치 수입니다. Decode Ways에서는 한 자리 단계에 1부터 9까지의 숫자가 필요하고 두 자리 단계에 10부터 26까지의 숫자가 필요하므로, 합의 각 항은 조건이 성립할 때만 더해집니다. 1로만 이루어진 문자열에서는 모든 단계가 가능하고, 그 경우의 수는 피보나치 수와 정확히 같습니다.

Decode Ways에서 0은 어떻게 처리하나요?

0은 단독으로 문자가 될 수 없으므로 앞에 있는 숫자와 짝을 이루어야 하며, 10과 20만 코드입니다. 상향식 반복문에서는 한 자리 숫자의 경우 0은 아무것도 더하지 않고, 1 또는 2 뒤에 오는 경우에만 두 자리 앞의 개수를 더합니다. 맨 앞에 0이 있거나, 0이 연속으로 두 개 있거나, 3부터 9까지의 숫자 뒤에 0이 오면 답은 0이 됩니다.

Decode Ways를 O(1) 공간으로 해결할 수 있나요?

네. 접두사의 개수는 한 자리와 두 자리 짧은 두 접두사의 개수에만 좌우되므로, 변수 두 개로 전체 표를 대체할 수 있습니다. 각 단계에서는 두 변수로부터 새로운 개수를 계산한 다음, 두 변수의 값을 한 위치씩 이동합니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "2611"

기대값

Decode Ways

함수

제약 조건

예제

힌트

풀이

재귀를 사용해 두 가지 읽기를 모두 시도해 보세요

메모를 사용한 재귀

두 개의 카운터를 사용한 상향식

함정과 경계 사례

자주 묻는 질문4

비슷한 문제