カッコを回転[プログラマー]

2351 ワード

かっこを回転
次の規則に従う文字列は、有効なカッコ文字列として定義されます.
  • ()、[]および{}は有効なカッコ文字列です.
  • Aが有効な括弧文字列である場合、(A)、[A]および{A}も有効な括弧文字列である.たとえば、[]は有効な括弧文字列であり、([])も有効な括弧文字列である.
  • A、Bが有効な括弧文字列であれば、ABも有効な括弧文字列である.たとえば、{}および([])は有効なカッコ文字列であり、{}([])も有効なカッコ文字列です.
  • パラメトリック文字列sは、四角カッコ、大かっこ、小かっこからなる.sをx(0≦x<(sの長さ)格子に左に回転すると、solution関数を完了し、sを正しいカッコ文字列にするxの個数を返します.
    せいげんじょうけん
    sの長さは1または1000以下である.
    I/O例

    I/O例説明
  • I/O例#1
  • 次の表は、「「」が回転していることを示します。 3つのxが有効なカッコ文字列であるため、3を返さなければなりません。2I/O例#2 次の表は、「}」()[{」の回転を示しています。 2つのxが有効なカッコ文字列であるため、2を返さなければなりません。 I/O例#3 sをどのように回転しても正しいカッコ文字列を作成できないため、0を返さなければなりません。 I/O例#4 sをどのように回転しても正しいカッコ文字列を作成できないため、0を返さなければなりません。 📌 問題解決策 1.インデックスを作成し、値を回転して繰り返す 2.閉じていない括弧をスタックに入れる 3.閉じた括弧の場合、popは同じ開いた括弧が現れるまで 4.()、{}、[]カッコ完了後カウント+1 5.文字列/2==「有効カッコ数」の場合、「有効カッコ文字列数」+1 6.return正しいかっこ文字列数 マイコード import sys def solution(s): c=0 cc=0 for i in range(len(s)): s=s[1:]+s[0] stack=[] for i in range(len(s)): a=s[i] if(a=="["or a=="(" or a=="{"): stack.append(a) else: while stack: b=stack.pop() if ((a==")" and b=="(") or (a=="}" and b=="{") or (a=="]" and b=="[")): c+=1 break if(c==len(s)/2): cc+=1 c=0 return cc s=sys.stdin.readline().strip() print(solution(s)) 😒コードコメント めちゃくちゃな感じで、修正してますます汚れてきました。また,二重再複文にwhileと書くと,時間的複雑さが増すようである. 簡潔に編みましょう。 複文を減らし、条件文を活用! その他のコードの分析 def solution(s): count = 0 i = 0 for i in range(len(s)): stack = [] for j in s: if not stack: stack.append(j) continue if stack[-1] == '[' and j == ']': stack.pop() elif stack[-1] == '{' and j == '}': stack.pop() elif stack[-1] == '(' and j == ')': stack.pop() else: stack.append(j) s = s[1:] + s[0] if not stack: count += 1 return count from collections import deque def check(s): while True: if "()" in s: s=s.replace("()","") elif "{}" in s: s=s.replace("{}","") elif "[]" in s: s=s.replace("[]","") else: return False if s else True def solution(s): ans = 0 que = deque(s) for i in range(len(s)): if check(''.join(que)): ans+=1 que.rotate(-1) return ans」を示しています.