문제 개요
숫자로 이루어진 문자열 s가 주어졌을 때, 이 문자열이 연속적으로 감소하는 정수, 즉 내림차순으로 이어지는 정수들을 포함하고 있는지 확인해야 합니다.
예를 들어 입력이 s = "99989796"이라면, 이 문자열은 [99, 98, 97, 96]으로 나눌 수 있으므로 결과는 True입니다.
해결 접근 방법
이 문제는 재귀(백트래킹) 방식으로 해결할 수 있습니다. 핵심 아이디어는 문자열의 앞부분에서 첫 번째 숫자를 잘라낸 뒤, 그 숫자보다 1 작은 값이 뒤따라 오는지 재귀적으로 검사하는 것입니다.
단계별 풀이 과정은 다음과 같습니다.
helper() 함수를 정의합니다. 이 함수는 현재 위치(pos)와 이전 숫자(prev_num)를 매개변수로 받습니다.
pos가 문자열 길이 n과 같다면, 모든 숫자를 성공적으로 매칭한 것이므로 True를 반환합니다.
num_digits := prev_num의 자릿수로 설정합니다.
i를 num_digits - 1부터 num_digits까지 반복합니다.
- s의 pos부터 pos+i-1까지 부분 문자열이 존재하고, 그 숫자 값이 prev_num - 1과 같다면 helper(pos + i, prev_num - 1)을 호출합니다.
- helper가 True를 반환하면 True를 반환합니다.
반복이 모두 실패하면 False를 반환합니다.
메인 메서드에서는 다음을 수행합니다.
- n := 문자열 s의 길이
- i를 1부터 n/2의 몫까지 반복하면서, s의 처음 i개 문자를 숫자로 변환해 num에 저장합니다.
- helper(i, num)이 True를 반환하면 True를 반환합니다.
모든 시도가 실패하면 최종적으로 False를 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, s):
n = len(s)
def helper(pos, prev_num):
if pos == n:
return True
num_digits = len(str(prev_num))
for i in range(num_digits - 1, num_digits + 1):
if s[pos:pos+i] and int(s[pos:pos+i]) == prev_num - 1:
if helper(pos + i, prev_num - 1):
return True
return False
for i in range(1, n // 2 + 1):
num = int(s[:i])
if helper(i, num):
return True
return False
ob = Solution()
s = "99989796"
print(ob.solve(s))
동작 원리
입력 "99989796"의 경우, 메인 루프에서 먼저 첫 두 자리인 "99"를 시작 숫자로 선택합니다. 이후 helper 함수는 다음 위치에서 "98"을 찾고, 이어서 "97", "96"을 차례대로 찾아냅니다. 마지막 숫자까지 매칭에 성공하면 pos가 n에 도달하여 True가 반환됩니다.
입력
"99989796"
출력
True