(雲LEVEL)abからbba

質問する

https://level.goorm.io/exam/51356/ab%EB%A5%BC-bba%EB%A1%9C/quiz/1

に答える

最初は2つのスタックを置く方法を考えました.ある位置の文字が「b」である場合、スタックのtopによって前の文字が何であるかを知る方法で、以下の機能が実現されます.

コード1

import java.io.*;
import java.util.*;

class Main {
	
	static int value = 1000000007;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		
		Stack<Character> s1 = new Stack<>();
		Stack<Character> s2 = new Stack<>();
		long count = 0;
		
		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
			
			if (c == 'a' || (s1.isEmpty() || s1.peek() == 'b')) {
				s1.push(c);
			} else {	
					count = (count + 1) % value;
					s1.pop();
					s2.push('a');
					s2.push('b');
					s2.push('b');
					
					while (!s2.isEmpty()) {
						char tmp = s2.pop();
						
						if (tmp == 'a' || (s1.isEmpty() || s1.peek() == 'b')) {
							s1.push(tmp);
						} else {
							count = (count + 1) % value;
							s1.pop();
							s2.push('a');
							s2.push('b');
							s2.push('b');
						}
					}
			}
		}
		
		System.out.println(count);
	}
}

答えを探しても問題はありませんが、実行中にエラーが発生しました.見逃したところがあるかどうかチェックしましたが、その問題ではありません.
文字列長は20万であり,abがbbaに変換されるにつれてスタック内の要素数が急激に増加し,最終的にスタック爆発を招いた.
このような問題が発生したのはdp問題の可能性が高い.よく見るとabをbbaに変換すると、文字列の長さとaの位置だけが変化し、aの個数は変わらない.
ex)
1. aaab -> aabba
2. aabba -> abbaba
3. abbaba -> bbababa
4. bbababa -> bbabbbaa
5. bbabbbaa -> bbbbabbaa
6. bbbbabbaa -> bbbbbbabaa
7. bbbbbbabaa -> bbbbbbbbaaa
aaabとbbbbbaaaのaはそれぞれ3つで,同じであった.
では、bの前のaの個数には規則があると思います.以下の規則が得られます.
ルール＃ルール＃
ab -> 1
aab -> 3
aaab -> 7
aaaab -> 15
...
dp[i]=dp[i-1]*2+1がわかる.
(ただし,問題で与えられたモジュール化演算を考慮する必要がある.
これらの性質を用いてコードを再記述した.

コード2

import java.io.*;
class Main {
	
	final static int value = 1000000007;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;
		int[] dp = new int[1000001];
		
		for (int i = 1; i < dp.length; i++) {
			dp[i] = (dp[i - 1] * 2 + 1) % value;
		}

		String input = br.readLine();
		
		int count = 0;
		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
			
			if (c == 'a') {
				count++;
			} else {
				answer = (answer + dp[count]) % value;
			}
		}
		
		System.out.println(answer);
	}
}