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)で解けるらしい。