leetcode : decode ways

Decode Ways - LeetCode

Decode Ways - LeetCode

 

전~~형적인 dp 문제다~~

dp는 규칙찾기부터 시작하지 말고 전체 탐색부터 시작한다.

전체 탐색에 메모만 딱 곁들이면 그게 dp니까.

 

dp 문제의 전체 탐색은 뭐다? 탐색 트리를 그리는 것부터 시작한다~~

저 숫자들은 '디코딩한 글자 수'다. 처음엔 아무것도 디코딩 안돼있으니까 0부터 시작하는거고

len(s)가 되면 문자열 디코딩을 끝낸거니까 그 노드가 탐색 트리의 단말 노드가 되겠다.

len(s) 넘는건 그냥 없는 걸로 처리해주고.

 

잘 보면 탐색 트리에 중복이 존재하는 걸 확인할 수 있다. 유레카~

 

전체 탐색 코드

def check_valid(s):
    if s[0] == '0':
        return False
    if int(s) > 26:
        return False
    return True

def helper(s, num):
    if num == len(s):
        return 1
    if num > len(s):
        return 0

    n1 = n2 = 0
    if check_valid(s[num]):
        n1 = helper(s, num + 1)
    if check_valid(s[num:num+2]):
        n2 = helper(s, num + 2)
    return n1 + n2

def numDecodings(s):
    return helper(s, 0)

 

Memoization 적용

memorization 메모리제이션

아니고

memoization 메모이제이션

이다.

오타가 아니다. 메모 한다는 뜻이다.

 

class Solution:
    def helper(self, dp, s, num):
        if dp[num] != -1:
            return dp[num]

        n1 = n2 = 0

        #이렇게 해둔 덕분에 밑에 validation을 통과하지 않으면 자연스레 리턴값이 0이되게 된다.       

        if s[num] != '0':
            dp[num + 1] = n1 = self.helper(dp, s, num + 1)
            
            if int(s[num:num+2]) <= 26:
                dp[num + 2] = n2 = self.helper(dp, s, num + 2)

        dp[num] = n1 + n2
        return dp[num]


    def numDecodings(self, s: str) -> int:
        dp = [-1] * (len(s) + 2)
        dp[len(s)] = 1 # 디코딩을 다 하면 1을 리턴하는 것
        dp[len(s) + 1] = 0 # string 길이를 넘어가면 0을 리턴하는 것
        return self.helper(dp, s, 0)

 

굵을 글씨 친 부분을 잘 보면 된다. (거의다 쳐져있는데?;;)

일단 속도 향상을 위해 check_valid 함수를 따로 만들지 않고 helper함수 안에 넣어버렸다.

그리고 dp배열을 len(s) + 2의 길이로 초기화 했다.

dp[len(s)] = 1 # helper(s, len(s)) = 1이어야 하니까

그리고 helper(s, len(s)+1)은 0이어야 하니까 dp[len(s)+1] = 0으로 뒀다.

이렇게 하면 helper 구현이 훨씬 더 깔끔해짐.

 

96.77% ㅋㅋㅋㅋ 엄청난 속도로 통과해버렸다.. ㄷㄷ

 

메모화 재귀로 96%? 아 ㅋㅋ 재귀 없는 낭만적인 dp 못참지 그럼..

 

재귀 없는 낭만dp

재귀 없이 구현해보자. 

재귀를 깔끔하게 없애려면 설계에 약간 변경이 필요해보인다. 지금은 dp[len(s)]와 dp[len(s)+1]이 base case로 각각 1과 0이기 때문이다. 지금과 같은 방법으로 구현하려면 iterator를 0부터 시작하는 아름다운 코드가 아니라 len(s)-1부터 역방향으로 가는 조금 찝찝한 코드가 되어버린다. (물론 그래도 상관 없을거같긴한데 갠적으로 0부터 채우는걸 좋아해서..ㅎ)

 

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)

        dp[0] = 1

        for i in range(len(s)):
            if s[i] != '0':
                dp[i + 1] += dp[i]

                if i+2 <= len(s) and int(s[i:i+2]) <= 26:
                    dp[i + 2] += dp[i]

        return dp[len(s)]

 

임의의 i에 대해서 dp[i] = dp[i-1] + dp[i-2] 식으로 구하는게 아니라

dp[i]값을 dp[i+1]과 dp[i+2]에 더해주는 방식으로 구현했다

이래야 0부터 시작하는 iteration 방식으로 구현하기 깔끔하다.

결국 iteration을 돌면서, 현재 loop에서는 dp[i+2]에 dp[i]가 더해질것이고 다음 loop에서 dp[i+1]이 더해질 것이다.

 

사실 실행속도는 서버 상황에 따라 달라질 수 있는거라 어쩔 수 없.. ㅋㅋㅋ

근데 memory usage는 찢..었..다.. 99.19 ㅋㅋㅋ

참고로 여기서 나오는 퍼센테이지는 내가 이 사람들보다 잘 했다는 뜻이다.

faster than 90.59%

less than 99.19%

 

근데 이 문제.. 잘 보면 불필요한 메모리 사용이 보인다..!

피보나치 수열 문제를 생각해보자.

피보나치 수열 역시 fib(n)을 구할 때 O(N) 스페이스의 메모리를 초기화해서 사용할 수 있지만

한번 계산된 값은 딱 두번 쓰이고 그 이상 안쓰이기 때문에 그냥 변수 세 개 만들어서 O(1) 스페이스로 구현이 가능하다.

이 문제도 마찬가지 아니야!?

 

O(1)로 구현하기

class Solution:
    def numDecodings(self, s: str) -> int:
        prv,cur,nxt = 1,0,0

        for i in range(len(s)):
            if s[i] != '0':
                cur += prv

                if int(s[i:i+2]) <= 26:
                    nxt += prv
            
            prv,cur,nxt = cur,nxt,0

        return prv

 

극한의 공간 절약

위에 코드가 보기는 깔끔한데 prv,cur,nxt = 1,0,0과 같이 튜플 대입 식을 사용하면 임시 튜플이 메모리를 먹기도 하고 s[i:i+2]같은 슬라이싱 연산 역시 배열을 복사하기 때문에 극한까지 절약하려면 다음과같이 해야한다. (사실 이럴필요까진 없는데 그냥.. 재밌어서 ㅎ)

class Solution:
    def numDecodings(self, s: str) -> int:
        prv = 1
        cur = 0
        nxt = 0

        for i in range(len(s)):
            if s[i] != '0':
                cur += prv

                if i<len(s)-1 and (ord(s[i])-48)*10 + ord(s[i+1])-48 <= 26:
                    nxt += prv
            
            prv = cur
            cur = nxt
            nxt = 0

        return prv

 

아 ㅋㅋ 식 풀어써버리자

class Solution:
    def numDecodings(self, s: str) -> int:
        prv = 1
        cur = 0
        nxt = 0

        for i in range(len(s)):
            if s[i] != '0':
                cur += prv

                if i<len(s)-1 and 10*ord(s[i])+ord(s[i+1]) - 555 < 0:
                    nxt += prv
            
            prv = cur
            cur = nxt
            nxt = 0

        return prv

갈데까지 가버렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 가독성 0!!!

 

역시 dp는 정말 꿀맛이다.

탐색 트리를 그리고 재귀로 구현한 다음에 메모화시키고 재귀를 없애는 이 과정 자체가 너무 즐겁다.

DP는 내 콤플렉스이기도 하다. 나는 알고리즘 문제를 정말 못 풀고 그 중 dp랑 graph는 최악이다.(둘이 코테에서 젤 중요한데..ㅎ) 지금 약간 dp콤플렉스를 극복하는 단계에 있는 듯하다. 나중에 다른 회사 코테를 보게되면 다른 문제는 못 풀어도 dp는 꼭 풀었으면 좋겠다.