3333. Find the Original Typed String II - Streak 9
주의: k가 "최소" 이다.
엘리스는 k개 이상의 문자를 입력하려고 했었다는 뜻이다.
몇가지 용어를 먼저 정의해두자.
- 문자 그룹: 문자가 바뀌기 전까지의 연속된 문자
- 문자 그룹의 문자 타입: 문자 그룹을 형성하는 문자
- k - 문자 그룹의 수 = 실제로 경우의수를 만드는 선택가능한 수
함수를 정의해보자.
f(현재 문자 그룹, 남은 선택 수)
독립변수
- 현재 문자 그룹 i: 몇 번째 문자 그룹인가?
- 남은 선택 수 x: 몇 개의 문자를 더 채워야 하는가?
종속변수
- i 문자 그룹부터 x개의 문자를 더 채워야할 때, 지금까지 채워온 경우의 수
점화식을 세워보자.
초기조건은 다음과 같이 설정 가능하다.
x = [1, tg[0]]에 대하여
이 연산에 모듈로를 씌워주면 답을 구할 수 있다.
i < 2000, x < 500000
총 10억 개의 정수를 보관해야 하므로, 약 8GB의 메모리가 필요하다.
너무 비효율적이다...
좀 더 좋은, 수학을 이용한 풀이가 없을까?
앞에서 다 털면 뒤에서 못쓰기 때문에, 앞에서 턴 갯수를 알고 있어야 하긴 하는데
다시 한번 문제를 재정의해보자.
1. tgCount >= k
이면, 제약이 자동으로 만족하므로, 답은
2. tgCount < k
이 경우에는 만든 문자열이 k보다 짧을 수 있으므로,
전체 길이 < k인 경우 (나쁜 경우)를 세서 전체 경우의 수에서 빼주자.
f(현재 문자 그룹, 남은 선택 수)
독립변수
- 현재 문자 그룹 i: 몇 번째 문자 그룹인가?
- 남은 선택 수 x: 몇 개의 문자를 더 채워야 하는가?
종속변수
- i 문자 그룹부터 x개의 문자를 더 채워야할 때, 지금까지 채워온 경우의 수
여기서 “남은 선택 수 x”는 각 그룹에서 최소 1개씩은 이미 뽑았다고 보고, 그 이후에 추가로 더 뽑아야 하는 개수를 의미하도록 두자.
그러면 한 그룹에서 추가로 뽑을 수 있는 범위는 0 ~ (그룹 길이 - 1)이 된다.
즉, 우리는 전체 길이 ≤ k-1 인 결과만을 찾고, 그걸 최대 결과에서 제거해주면 된다.
이러면, 탐색해야 하는 범위가 대폭 줄어든다(k 이하).
이 관점에서 “전체 길이 ≤ k-1”을 세려면,
- “각 그룹에서 최소 1개씩 뽑은 뒤 추가로 채운 총합”이 0 ~ (k−1)−(문자 그룹의 수) 이하여야 한다.
다시, 점화식
점화식
초기조건
이때, 누적합을 이용해 이전 인덱스의 값을 구할 때 사용했던 값들을 재이용하면 더욱 빠르게 계산할 수 있다.
public class Solution {
static final int MOD = 1_000_000_007;
public int possibleStringCount(String word, int k) {
int n = word.length();
List<Integer> tg = new ArrayList<>();
int cnt = 1;
for (int i = 1; i < n; i++) {
if (word.charAt(i) == word.charAt(i - 1)) cnt++;
else { tg.add(cnt); cnt = 1; }
}
tg.add(cnt);
int groupCount = tg.size();
long totalLen = n;
long allWays = 1;
for (int len : tg) allWays = (allWays * len) % MOD;
if (k <= groupCount) return (int) allWays;
if (k > totalLen) return 0;
int maxX = (k - 1) - groupCount;
int[] prev = new int[maxX + 1];
int[] curr = new int[maxX + 1];
int firstMax = Math.min(maxX, tg.get(0) - 1);
for (int x = 0; x <= firstMax; x++) prev[x] = 1;
for (int i = 1; i < groupCount; i++) {
Arrays.fill(curr, 0);
int window = tg.get(i);
long windowSum = 0;
for (int x = 0; x <= maxX; x++) {
windowSum += prev[x];
if (windowSum >= MOD) windowSum -= MOD;
if (x - window >= 0) {
windowSum -= prev[x - window];
if (windowSum < 0) windowSum += MOD;
}
curr[x] = (int) windowSum;
}
int[] tmp = prev;
prev = curr;
curr = tmp;
}
long bad = 0;
for (int x = 0; x <= maxX; x++) {
bad += prev[x];
if (bad >= MOD) bad -= MOD;
}
long ans = (allWays - bad) % MOD;
if (ans < 0) ans += MOD;
return (int) ans;
}
}문제를 처음부터 정확히 읽자