0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

机の上に N 個のキューブが縦に積まれています。長さ N の文字列 S が与えられます。

下から i 番目のキューブの色は、 S の i 文字目が 0 のとき赤色、1 のとき青色です。

あなたは、赤色のキューブと青色のキューブが隣り合っているような部分を選んで、それら 2 個のキューブを取り除く操作を何度でも行えます。

このとき、取り除いたキューブの上にあったキューブは真下の物体の上に落下します。

最大で何個のキューブを取り除けるでしょうか。

2.入力例

入力：

11011010001011

出力：

3.初見の感想

再帰的に1と0が含まれてる部分を探して、文字列を小さくする方法を考えました
するとTLEになりました(悲しい…)

4.学びポイント

どうやったら一回のループで計算できるか…
スタックを使いましょう！
ちなみにこの問題は0と1の個数の差が答えになるので、その方法でも解けます(これが一番簡単だと思います…)

5.コードの簡単な解説

一文字ずつ読み込んでスタックに積みます、10,01のように消える場合ならPopして消します

 for (int i = 0; i < str.Length; i++)
        {
            stack.Push(str[i]);
            if (stack.Count > 1)
            {
                var a = stack.Pop();
                var b = stack.Pop();
                if (a != b)
                {
                    count += 2;
                }
                else
                {
                    stack.Push(b);
                    stack.Push(a);
                }
            }
        }

6.全コード

using System;
using System.Collections.Generic;

public class Program
{
    static void Main()
    {
        var str = Console.ReadLine();
        var stack = new Stack<char>();
        var count = 0;
        for (int i = 0; i < str.Length; i++)
        {
            stack.Push(str[i]);
            if (stack.Count > 1)
            {
                var a = stack.Pop();
                var b = stack.Pop();
                if (a != b)
                {
                    count += 2;
                }
                else
                {
                    stack.Push(b);
                    stack.Push(a);
                }
            }
        }

        Console.WriteLine(count);
    }
}

7.最後に

そろそろ計算量にも目を向けていきたいですね…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】AtCoder Beginner Contest 120③