【競技プログラミング】AtCoder Beginner Contest 307_D問題

問題

要約

1. 長さNの文字列Sが与えられる。
2. Sは英小文字と括弧 ( ) で構成されている。
3. 以下の操作を可能な限り繰り返す：
   • Sの連続部分文字列で、以下の条件を満たすものを1つ選んで削除する
     • 最初の文字が (
     • 最後の文字が )
     • 最初と最後以外に ( や ) を含まない
4. 操作を繰り返した後の最終的なSを出力します。

• N: 文字列Sの長さ
• S: 与えられる文字列

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

スタックを使用して、括弧で囲まれた部分を処理する。
文字列を左から右へ走査し、開き括弧 "(" に遭遇したら新しいグループをスタックに追加する。
閉じ括弧 ")" に遭遇したら、対応する開き括弧があればそのグループを削除し、なければ結果に追加する。
英小文字はスタックの最上位のグループに追加するか、スタックが空の場合は結果に直接追加する。
最後に、スタックに残っているグループを結果に追加して最終的な文字列を得る。

解法手順

1. 入力を受け取り、文字列Sを1文字ずつ処理する準備をする。
2. 空のスタックと結果リストを用意する。
3. Sの各文字に対して以下の処理を行う：
   • 文字が "(" の場合、新しいグループとしてスタックに追加する。
   • 文字が ")" の場合：
     • スタックが空でなければ、最後のグループを削除（対応する括弧を削除）。
     • スタックが空なら、結果リストに ")" を追加。
   • それ以外の文字（英小文字）の場合：
     • スタックが空でなければ、最後のグループに文字を追加。
     • スタックが空なら、結果リストに文字を追加。
4. スタックに残っているグループがあれば、それらを順番に結果リストに追加する。
5. 結果リストの文字を連結して最終的な文字列を作成し、出力する。

ACコード

ac.py

def io_func():
    # 入力を受け取る
    N = int(input())  # 文字列の長さ（この問題では使用しない）
    S = input()  # 処理する文字列
    return S

def solve(S):
    stack = []  # 括弧のグループを管理するスタック
    ans = []  # 結果を格納するリスト

    for s in S:
        if s == "(":
            # 開き括弧の場合、新しいグループをスタックに追加
            stack.append(["("])
        elif s == ")":
            if stack:
                # 閉じ括弧で、対応する開き括弧がある場合、グループを削除
                stack.pop()
            else:
                # 対応する開き括弧がない場合、結果に追加
                ans.append(s)
        else:
            if stack:
                # スタックが空でない場合、最後のグループに文字を追加
                stack[-1].append(s)
            else:
                # スタックが空の場合、結果に直接追加
                ans.append(s)

    # スタックに残っているグループを結果に追加
    for s in stack:
        ans += s

    # 結果のリストを文字列に変換して返す
    return "".join(ans)

if __name__=="__main__":
    # メイン処理
    S = io_func()
    result = solve(S)
    print(result)

###
# - N: 入力文字列の長さ（この問題では使用しない）
# - S: 処理する入力文字列
# - stack: 括弧のグループを管理するスタック
# - ans: 結果を格納するリスト
# - s: 文字列Sの各文字

# 1. io_func関数:
#    - 標準入力から文字列の長さNと文字列Sを読み取る
#    - 文字列Sを返す
# 2. solve関数:
#    - 入力文字列Sを受け取り、処理を行う
#    - スタック(stack)と結果リスト(ans)を初期化
#    - 文字列Sの各文字に対して以下の処理を行う:
#      a. 開き括弧"("の場合、新しいグループをスタックに追加
#      b. 閉じ括弧")"の場合:
#         - スタックが空でなければ、最後のグループを削除
#         - スタックが空なら、結果リストに")"を追加
#      c. それ以外の文字（英小文字）の場合:
#         - スタックが空でなければ、最後のグループに文字を追加
#         - スタックが空なら、結果リストに文字を追加
#    - スタックに残っているグループを結果リストに追加
#    - 結果リストを文字列に変換して返す
# 3. メイン処理:
#    - io_func関数を呼び出して入力を取得
#    - solve関数を呼び出して結果を得る
#    - 結果を出力する```