yukicoder No.457 (^^*)

左カッコ一つ一つに対して、文字列の最後まで探索し、その間に現れる左向きと右向きの数を数え上げる。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		
		//左向きの個数と右向きの個数をカウントする変数
		int L = 0;
		int R = 0;
		
		//一時的な文字列としてStringBuilderを利用する
		StringBuilder l = new StringBuilder();
		StringBuilder r = new StringBuilder();
		
		//すべての左カッコについて調べる
		for (int i=0; i<s.length(); i++) {
			//左カッコを検出
			if (s.charAt(i)=='(') {
				//左カッコならば、文字列の末尾まで探索
				for (int j=i+1; j<s.length(); j++) {
					char c = s.charAt(j);
					//*の場合と^の場合とで、それぞれ左向きと右向きとを作っていく
					if (c=='*') {
						if (r.length()==0) {r.append("*");}
						if (l.length()==2) {l.append("*");}
					}
					else if (c=='^') {
						if (r.length()==1 || r.length()==2) {r.append("^");}
						if (l.length()==0 || l.length()==1) {l.append("^");}
					}
					//右カッコが現れたとき、左向きor右向きが完成していればカウント。
					else if (c==')') {
						if (r.length()==3) {R++;}
						if (l.length()==3) {L++;}
					}
				}
				//一つの左カッコを調べ終わったら、左向きと右向きをリセット。
				r.setLength(0);
				l.setLength(0);
			}
		}
		
		System.out.println(L+" "+R);
	}
}

サンプル5を例にして説明する。

・(*^^)*(^^*)

左カッコは2個あるので、それぞれの左カッコについて文字列の末尾まで調べる。

1番目の左カッコを調べるときの流れを下に書いてみる。左向きがソースコード中の"l"、右向きがソースコード中の"r"に対応する。

・*　　左向き0：右向き0[*]
・*^　　左向き0[^]：右向き0[*^]
・*^^　　左向き0[^^]：右向き0[*^^]
・*^^)　　左向き0[^^]：右向き1[*^^]　

完成しているときに右カッコが現れたので右向き+1。以降、*や^が現れても、右向きのに付け足す必要はない（カッコ以外は何回でも使えるため）。

・*^^)*　　左向き0[^^*]：右向き1[*^^]
・*^^)*(　　変化なし　いまは1番目の左カッコについて調べているので、左カッコが出てきても無視。
・*^^)*(^　　変化なし
・*^^)*(^^　　変化なし
・*^^)*(^^*)　　左向き1[^^*]：右向き2[*^^]　＜処理終了＞

というふうにして、1番目の左カッコについて調べた結果、左向き1、右向き2という結果が得られた。この処理を同様に2番目の左カッコに対しても行ってやると、左向き1となる。よって、左向き2、右向き2という出力が得られる。

この解法の時間計算量は、Nを文字列の長さとしたとき、おそらくO(N*logN)だと思われる。動的計画法を使えばO(N)で解けるらしい。