一次元リバーシ / 1D Reversi [AtCoder Beginner Contest 047 C]

atcoder.jp

まず思いついたのは全探索解法です。

・石を左端に置くか右端に置くか
・石の色は黒か白か

この4パターンから、裏返せる石の数が最多であるものを選び、そのつど石を裏返しながら手数を数えていくというものです。文字列長が 10 くらいなら現実的な解法なのかもしれませんが、今回の S の長さは 10^5 です。非現実的です。したがって、計算量 O(N) くらいの解法を考えなければなりません。

あまりこういうやり方はよくないと思うんですが、出力例から帰納的に考えてみます。

・BBBWW　→　1
・WWWWWW　→　0
・WBWBWBWBWB　→　9

あっもしかして、文字列を左から見ていったときの、色が変化した回数が答えになるんじゃないか、と気づきました。そこで以下のようなコードを提出したところ無事に AC できました。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		String s = sc.next();
		
		int ans = 0;
		int color = s.charAt(0);
		for (int i=0; i<s.length(); i++) {
			if (color != s.charAt(i)) {
				ans++;
				color = s.charAt(i);
			}
		}
		
		System.out.println(ans);
		
	}
}

今回は color 変数を持って先頭から1文字ずつ見ていきましたが、隣り合う2文字を順に見ていったとき異なるものは何個あるか、という方法でも解けると思います。