白駿9012号:かっこ

質問する

https://www.acmicpc.net/problem/9012

スタックを使用するナビゲーション範囲(ナビゲーションを継続する必要がある値のみを残す)を削減する

.

きろくてん

スタックやキューのコアを利用するのも、探索範囲を効率的に管理するためです!

「スタックを使用して問題を解決しました.」

「スタックを使って不要な探索を減らす!」問題を正しく理解する

特定のデータ構造を使用してナビゲーションターゲットを整理し、ナビゲーション範囲を縮小できることを覚えます.

の並べ替えられていないターゲットを繰り返しブラウズする場合、

は、従来のアレイ

ではなくスタックやキューなどのデータ構造を採用する.

次ラウンドのナビゲーションを必要としない値を除去し、

ナビゲーション範囲

を縮小することができる.

方法

九九

"(カッコを付けて")は閉じたカッコで、

四角カッコに一致する丸カッコ(または四角カッコに一致する丸カッコ)を検索し、一致しない丸カッコがないことを確認します.

スタック使用率

が「(()()」と題した場合、

字で吟味して解くと、最後の「)」が誰と一致するかを見つけるために、すべての「(」が確認されなければならない.

ただし、他の「」と一致している「(」は確定する必要はありません)

したがって、スタックを使用することにより、中間一致する項目を削除することができ、ナビゲーション範囲

を低減することができる.

回答の提出

スタック使用率

import sys
N = int(sys.stdin.readline())
for i in range(N):
    # 괄호 문자열 확인
    target = sys.stdin.readline().rstrip()
    # 스택 생성
    stack = []
    is_valid = True
    # 각 문자열에 대한 탐색
    for c in target:
        # '여는 괄호'인 경우, 탐색 범위(스택)에 추가
        if c == "(": 
            stack.append(c)
            continue
        # '닫는 괄호'인데, 스택이 비어 있는 경우 (즉, 매칭할 '여는 괄호'가 없는 경우)
        if len(stack) == 0:
            is_valid = False
            break
        # 이번 '닫는 괄호'와 매칭되는 '여는 괄호'를 탐색 범위에서 제외
        # (이에 따라 다음에 등장하는 '닫는 괄호'는 이미 매칭된 '여는 괄호'를 탐색할 필요가 없음)
        stack.pop()
        
    # 매칭되지 않은 '여는 괄호'가 탐색 범위에 남아 있는지 확인
    if len(stack) > 0:
        is_valid = False
        
    if is_valid: 
        print("YES")
    else: 
        print("NO")

簡略化された答え

import sys
N = int(sys.stdin.readline())
for i in range(N):
    target = sys.stdin.readline().rstrip()
    stack = 0
    for c in target:
        if c == "(": 
            stack += 1
        else: 
            stack -= 1
        if stack < 0:
            break
    if stack == 0: print("YES")
    else: print("NO")