문제 개요
숫자로만 구성된 문자열 s가 주어졌다고 가정해 보겠습니다. 이때 s를 두 개 이상의 비어 있지 않은 부분 문자열로 분할하되, 각 부분 문자열의 숫자 값이 내림차순을 이루고 인접한 두 값의 차이가 정확히 1이 되도록 할 수 있는지 확인해야 합니다.
예를 들어 문자열이 s = "0080079"라면 ["0080", "079"]로 분할할 수 있으며, 각 부분의 숫자 값은 [80, 79]가 됩니다. 값이 내림차순으로 배치되어 있고 인접한 값의 차이가 1이므로 이 분할은 유효합니다. 우리가 확인해야 할 것은 s를 위와 같은 조건에 맞게 분할하는 것이 가능한지 여부입니다.
입력이 s = "080076"이라면 출력은 True가 됩니다. ["08", "007", "6"]처럼 분할하면 숫자 값이 [8, 7, 6]이 되어 조건을 만족하기 때문입니다.
해결 접근 방식
이 문제는 깊이 우선 탐색(DFS)을 활용해 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- dfs() 함수를 정의합니다. 이 함수는 s, pre, idx, n 네 개의 매개변수를 받습니다.
- pre가 -1이 아니고, 문자열 s[idx:]를 정수로 변환한 값이 pre - 1과 같다면 True를 반환합니다.
- i를 1부터 n-idx까지 반복하면서 다음을 수행합니다.
- curs := s[idx : idx+i] (현재 부분 문자열)
- cur := curs를 정수로 변환한 값
- pre가 -1이라면(아직 이전 값이 없는 경우):
- dfs(s, cur, idx+i, n)이 참이면 True를 반환합니다.
- 그렇지 않은 경우:
- cur가 pre - 1과 같고 dfs(s, cur, idx+i, n)이 참이면 True를 반환합니다.
- 모든 경우를 확인한 뒤에는 False를 반환합니다.
- 메인 함수에서는 다음을 수행합니다.
- n := 문자열 s의 길이
- n <= 1이면 False를 반환합니다(두 개 이상으로 나눌 수 없기 때문).
- dfs(s, -1, 0, n)의 결과를 반환합니다.
예제 코드
아래 구현 예시를 통해 더 잘 이해해 보겠습니다.
def dfs(s, pre, idx, n):
if pre != -1 and int(s[idx:]) == pre - 1:
return True
for i in range(1, n-idx):
curs = s[idx: idx+i]
cur = int(curs)
if pre == -1:
if dfs(s, cur, idx+i, n):
return True
else:
if cur == pre - 1 and dfs(s, cur, idx+i, n):
return True
return False
def solve(s):
n = len(s)
if n <= 1:
return False
return dfs(s, -1, 0, n)
s = "080076"
print(solve(s))입력
"080076"
출력
True
코드 설명
dfs 함수는 현재 위치 idx부터 시작해 가능한 모든 길이의 부분 문자열을 시도합니다. 첫 번째 값(pre == -1)일 때는 어떤 값이든 자유롭게 선택할 수 있고, 그 이후에는 반드시 이전 값보다 1작은 값만 선택할 수 있습니다. 남은 문자열 전체가 마지막 선택된 값보다 정확히 1작다면 분할이 성공한 것이므로 즉시 True를 반환합니다. 이러한 백트래킹 방식을 통해 문자열을 내림차순 연속 값으로 분할 가능한지 효율적으로 판단할 수 있습니다.