Leetcode 1849. Splitting a String Into Descending Consecutive Values - Python

Leetcode 1849 문제 보기

 

문제 이해하기

0 ~ 9까지의 숫자로 이루어진 문자열 s를 2개 이상의 substring으로 나눠보자.

이 때 각 substring들이 바로 이전의 substring에 비해 1이 작은 수로 이루어져 있다면,

즉 "substring = previous_substring - 1"일 경우, true를 return하는 프로그램을 작성하라.

 

각각의 substring은 빈 문자열이서는 안되며, substring은 1개 이상, 20개 이하의 숫자로 이루어져있다.

또한 1 ~ 9 이전에 등장하는 "0"은 무시해도 된다. 즉, "05" 은 숫자 5다.

 

아이디어 구상

Decision Tree를 그리며 생각해보자.

s = "050043"인 test case를 살펴보자.

By Mesotes

 

적어도 한 번은 s를 나눠야하므로, 첫 번째 substring은 첫 번째 숫자인 0부터 시작해서 마지막 숫자인 3을 제외한 05004까지 존재가능하다.

 

두 번째 substring부터는 위와 같은 제약사항은 존재하지 않는다.

다만, 바로 이전의 substring보다 1이 작을 경우에만 탐색을 지속하고 그렇지 않다면 가지치기한다.

예를 들어, "05"에 비해 "0"은 1 작지 않다. 이 때는 더 이상 해당 가지에 대해 탐색을 진행할 필요가 없다.

 

따라서 본 문제는 Backtracking를 활용한 DFS로 탐색을 진행하면서, 만약 주어진 s를 전부 탐색했을 때까지 true라면 최종적으로 true를 return하는 방식으로 해결가능하다.

 

이 때의 시간복잡도는 어떻게 될까?

n = len(s)라 했을 때, n개의 경우의 수에 대해 대략 n번씩 탐색을 해야한다.

즉, 최악의 경우 Time Complexity ~ O(n ^ n)의 시간복잡도가 나온다.

 

그러나 Backtracking을 적절히 사용하므로, 실제 시간 복잡도는 이보다 나을 것으로 생각된다.

 

풀이

문제 풀이를 위해 필요한 도구(변수, 함수 등)들을 생각해보자.

우선 dfs()가 필요하다.

탐색 종료 시까지 true라면 최종적으로 true를 반환하면 되기 때문에 따로 결과 등을 담을 리스트는 필요없겠다.

def dfs()

 

첫 번째 substring은 이후의 substring과 달리 제약조건(s의 마지막 숫자는 제외)이 있기 때문에, 반복문을 통해 트리의 첫 번째 level에 해당하는 경우의 수들을 구해주자. 그리고 이들을 dfs()의 argument로 삼는다.

for i in range(len(s) - 1):
    val = int(s[:i + 1])
    if dfs(i + 1, val): return True

 

dfs()를 구현해보자.

 

우선 base case는 다음과 같다.

s를 탐색할 때 사용하는 index가 len(s)와 같아질 때 leaf node에 도달할 것이며, 탐색이 완료되었다는 뜻이므로 true를 return한다.

if index == len(s):
    return True

 

재귀 부분은 다음과 같다.

현재 구한 substring이 이전의 substring에서 1을 뺀 값이라면 다음 index에 대해 dfs()를 계속 진행한다.

for j in range(index, len(s)):
    val = int(s[index:j + 1])
    if pre_val - 1 == val and dfs(j + 1, val):
        return True
return False

 

전체 코드는 다음과 같다.

class Solution:
    def splitString(self, s: str) -> bool:
        
        
        def dfs(index, pre_val):
            # base case
            if index == len(s):
                return True
            
            for j in range(index, len(s)):
                val = int(s[index:j + 1])
                if pre_val - 1 == val and dfs(j + 1, val):
                    return True
            return False
                    
        for i in range(len(s) - 1): # the first level cannot include the last character
            val = int(s[:i + 1])
            if dfs(i + 1, val): return True
            
        return False

 

---

Leetcode 1849. Splitting a String Into Descending Consecutive Values

https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/​​

 

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다