✔Algorithm/programmer/2017降格/レベル2/ペアリング削除を求める(Python使用)
5388 ワード
📖 質問する
📝 解法1(効率x)
すべての文字列をチェックする直感的な方法で問題を解きます.
すべての文字列をチェックする直感的な方法で問題を解きます.
΄コード1(エラーコード)
例えば、sが「ababababa」である場合、隣接する2つのアルファベットを検索する場合、for文はn/2の周りを回り、全n/2ペアが消去されるため、O(n/2*n/2)=O(n^2)
def solution(s):
# i는 문자열 index iterator
i = 0
while i < len(s)-1:
if s[i] == s[i+1]:
s = s.replace(s[i:i+2], '')
i = 0
else:
# 다음 인덱스 검사
i += 1
if len(s) == 0:
return 1
else:
return 0
📝 解題過程
stackが空でない場合は、現在の文字とstack topを比較します.
そうでない場合、現在の文字はスタック
空でない場合は、ペアリング
コード2 from collections import deque
def solution(s):
stack = deque()
for i in s:
# stack이 비어있을 경우
if not stack:
stack.append(i)
# stack이 비어있지 않고, stack top이 현재 문자 i와 같다면
elif stack[-1]==i:
stack.pop()
# stack이 비어있지 않고, stack top이 현재 문자 i와 같지 않다면
else:
stack.append(i)
if stack:
return 0
else:
return 1
Reference
この問題について(✔Algorithm/programmer/2017降格/レベル2/ペアリング削除を求める(Python使用)), 我々は、より多くの情報をここで見つけました
https://velog.io/@yellowsummer/Algorithmprogrammers2017팁스다운level2짝지어-제거하기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
from collections import deque
def solution(s):
stack = deque()
for i in s:
# stack이 비어있을 경우
if not stack:
stack.append(i)
# stack이 비어있지 않고, stack top이 현재 문자 i와 같다면
elif stack[-1]==i:
stack.pop()
# stack이 비어있지 않고, stack top이 현재 문자 i와 같지 않다면
else:
stack.append(i)
if stack:
return 0
else:
return 1
Reference
この問題について(✔Algorithm/programmer/2017降格/レベル2/ペアリング削除を求める(Python使用)), 我々は、より多くの情報をここで見つけました https://velog.io/@yellowsummer/Algorithmprogrammers2017팁스다운level2짝지어-제거하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol