"Find the Original Typed String II" 문제 요약 및 분석

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

웹 개발, 알고리즘, 동적 프로그래밍

대상자

• 알고리즘 문제 해결에 관심 있는 개발자
• 중급 이상의 프로그래밍 능력을 가진 사람
• 동적 프로그래밍과 조합론을 익히고자 하는 사람들

핵심 요약

• 문제의 핵심은 반복된 문자 그룹에서 원래 입력 가능한 문자 수를 계산하고, 그 중 길이가 k 이상인 경우만 선택하는 것
• 총 가능한 원본 문자 수는 각 반복 그룹에서 선택할 수 있는 경우 수를 곱하여 계산
• 길이가 k 미만인 경우는 동적 프로그래밍(DP)을 통해 계산하고, 총 수에서 제외
• 모듈로 연산은 10^9 + 7을 사용

섹션별 세부 요약

1. 문제 정의 및 입력 조건

• 입력값은 word (문자열) 및 k (최소 길이)로 구성
• word는 반복된 문자 그룹이 포함될 수 있음
• 반환값은 k 이상의 가능한 원본 문자 수

2. 반복 그룹 처리

• word를 반복된 문자 그룹으로 분할
• 예: "aaabbbcc" → ['aaa', 'bbb', 'cc']
• 각 그룹에서 선택 가능한 원본 문자 수는 g (그룹 길이)에 따라 g 가지
• 예: "aaa" → 1, 2, 3 중 하나 선택

3. 총 가능한 원본 문자 수 계산

• 각 반복 그룹의 가능한 선택 수를 곱하여 총 가능 수 계산
• 예: ["aaa", "bbb"] → 3 * 3 = 9 가지

4. 동적 프로그래밍(DP)을 통한 `k` 미만 길이 문자 수 계산

• dp[i] = 길이 i 이하의 가능한 원본 문자 수
• dp 배열을 이용하여 k 미만인 경우의 수를 계산
• dp 배열을 반복 그룹 수에 따라 업데이트

5. 최종 결과 계산

• 총 가능 수에서 k 미만인 경우를 뺄셈하여 k 이상인 경우만 계산
• 모든 연산은 10^9 + 7에 대한 모듈로 연산 적용

결론

• 반복된 문자 그룹을 분리하고, 각 그룹에서 가능한 선택 수를 곱하여 총 가능 수를 구한 후, k 미만인 경우를 동적 프로그래밍으로 계산하여 뺄셈하는 방식
• 10^9 + 7 모듈로 연산을 사용하여 큰 수를 처리
• k 값을 조정하여 다양한 경우에 적용 가능