【競プロ典型90問】「002 - Encyclopedia of Parentheses(★3)」解法
Free-PhotosによるPixabayからの画像

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。

問題

002 - Encyclopedia of Parentheses(★3)

ポイント

長さがNとなる「(」と「)」の組み合わせを全て試し、正しいカッコ列かどうかを検証します。

Pythonで組み合わせを生成するにはitertoolsのcombinationsを使用すると便利です。

正しいカッコ列かどうかを検証するには「(」を1、「)」を-1としてカッコ列の左から順番に加算していきます。正しいカッコ列ではない条件は以下の2つです。

①途中で-1となる

 例:()())( ※左から加算していくと1→0→1→0→-1→0 となります。

②最後まで加算したときに0になっていない

 例:()(())( ※左から加算していくと1→0→1→2→1→0→1 となります。

以上を踏まえ、実装したコードがこちらです。

コード

def main():
    import sys
    import itertools
    sys.setrecursionlimit(10 ** 9)
    input = sys.stdin.readline

    N = int(input())
    comb = list(itertools.product(['(', ')'], repeat=N))  # 組み合わせの生成

    ans = []
    for c in comb:
        cnt = 0
        for i in range(len(c)):
            if c[i] == '(':
                cnt += 1
            else:
                cnt -= 1
            if cnt == -1:  # 途中で-1となれば正しいカッコ列ではない
                break
        else:
            if cnt == 0:  # 最後まで加算したときに0になっていれば正しいカッコ列
                ans.append(c)

    print(*[''.join(a) for a in ans], sep='\n')


if __name__ == '__main__':
    main()

おすすめの記事