240405 안티세포

List<Map<Long, Integer>> levels;
long[] sum;
static final int MOD = 1000000007;

public int[] solution(int[] a, int[] s) {
	int[] answer = new int[s.length];
	int end = 0;

	for (int index = 0; index < s.length; index++) {
		int groupSize = s[index];
		int start = end;
		end = start + groupSize;
		sum = new long[groupSize + 1];
		sum[0] = 1;

		levels = new ArrayList<>();
		for (int i = 0; i <= groupSize; i++) {
			levels.add(new HashMap<>());
		}

		levels.get(0).put(-1L, -1);

		for (int i = 1; i <= groupSize; i++) {
			sum[i] = connect(a[start + i - 1], i, i - 1);
		}

		answer[index] = (int) ((sum[groupSize]) % MOD);
	}

	return answer;
}

long connect(long cellSize, int currentLevel, int parentLevel) {
	Map<Long, Integer> level = levels.get(currentLevel);
	level.computeIfAbsent(cellSize, k -> parentLevel);

	long result = sum[parentLevel];

	if (levels.get(parentLevel).containsKey(cellSize)) {
		result += connect(cellSize * 2, currentLevel, levels.get(parentLevel).get(cellSize));
		result %= MOD;
	}

	return result;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/86054