소문자로만 이루어진 문자열 i와 하나의 정수 j가 주어졌다고 가정해 봅시다. 이때 다음 세 가지 조건을 모두 만족하는 문자열이 총 몇 개인지 구해야 합니다.
- 문자열 i와 길이가 같아야 합니다.
- 사전순(lexicographically)으로 i보다 작거나 같아야 합니다.
- 같은 문자가 연속으로 나오는 횟수가 j를 초과하지 않아야 합니다.
정답은 결과를 10^9 + 7로 나눈 나머지(modulo) 형태로 계산해야 합니다.
예를 들어 입력이 i = "app", j = 2라면 출력은 405가 됩니다.
해결 접근 방법
이 문제는 각 자리마다 가능한 문자를 하나씩 결정해 나가는 자릿수 DP(Digit DP) 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- j <= 0이라면 조건을 만족하는 문자열이 없으므로 0을 반환합니다.
- m := 10^9 + 7 (모듈러 상수)
- n := 문자열 i의 길이
- nums := 문자열의 각 문자를 (문자의 유니코드 값 − 'a'의 유니코드 값)으로 변환한 리스트. 즉 'a'는 0, 'b'는 1처럼 0~25 범위의 숫자로 바꿉니다.
- dp(pos, bound, last, count) 함수를 정의합니다.
- count > j이면 조건 위반이므로 0을 반환합니다.
- pos == n이면 문자열을 끝까지 완성한 것이므로 1을 반환합니다.
- num := nums[pos] (현재 위치의 기준 문자)
- res := 0
- bound가 참이면 0부터 num까지, 그렇지 않으면 0부터 25까지 반복하며 다음을 수행합니다.
- res := res + dp(pos + 1, bound이고 i == num일 때만 참, i, count × (i == last일 때 참) + 1)
- res를 반환합니다.
- 메인 로직에서는 dp(0, True, -1, 0) % m을 반환합니다.
여기서 bound는 지금까지 만든 접두사가 원본 문자열과 완전히 일치하는지를 나타냅니다. bound가 참이면 현재 자리에서 원본 문자보다 큰 문자는 선택할 수 없고, 한 번이라도 작은 문자를 선택하면 이후 자리는 자유롭게 26개 문자를 모두 사용할 수 있습니다. last는 직전에 선택한 문자, count는 해당 문자가 연속으로 등장한 횟수를 추적합니다.
구현 예제
이해를 돕기 위해 실제 파이썬 구현을 살펴보겠습니다.
class Solution:
def solve(self, s, k):
if k <= 0:
return 0
MOD = 10 ** 9 + 7
n = len(s)
nums = [ord(char) - ord("a") for char in s]
def dp(pos, bound, last, count):
if count > k:
return 0
if pos == n:
return 1
num = nums[pos]
res = 0
for i in range(num + 1 if bound else 26):
res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
return res
return dp(0, True, -1, 0) % MOD
ob = Solution()
print(ob.solve('app',2))
입력
i = "app"
j = 2
출력
405
동작 원리 요약
위 코드에서 count * (i == last) + 1 부분이 핵심입니다. 현재 선택한 문자가 직전 문자와 같으면 연속 횟수가 1 증가하고, 다른 문자라면 연속 횟수가 1로 초기화됩니다. 이렇게 하면서 문자열을 앞에서부터 한 글자씩 채워 나가고, 마지막 자리까지 도달한 경우만 1로 세어 전체 경우의 수를 누적합니다.
참고로 문자열 길이가 길어지면 재귀 호출이 많아질 수 있으므로, functools.lru_cache 등을 활용해 메모이제이션을 추가하면 실행 속도를 크게 개선할 수 있습니다.