✔Algorithm/programmer/2017降格/レベル2/ペアリング削除を求める(Python使用)


📖 質問する



📝 解法1(効率x)


すべての文字列をチェックする直感的な方法で問題を解きます.
  • 文字列内に隣接する2つのアルファベットが見つかり、「」(空の文字列)で置き換えられます.
  • whileがドアの外から出たとき、sが空の文字列であれば、ペアリング削除は成功した.
  • whileがドアの外から出たとき、sが空の文字列でなければ、ペアリング削除に失敗します.
  • ΄コード1(エラーコード)

  • 時間複雑度はO(n^2)であり,効率試験は合格しなかった.
    例えば、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

    📝 解題過程

  • スタックを使用します.(「質問」で見つけた答え方🥺)
  • 文字列の文字を1つずつ巡回します.
  • スタックが空の場合、現在の文字はスタックにプッシュされます.
    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