📖 문제

📝 풀이 과정1(효율성 x)

모든 문자열을 검사하는 직관적인 방식으로 문제를 풀었다.

• 문자열 내에서 2개 붙어있는 알파벳을 찾아서 ''(빈 문자열)로 대체한다.
• while문 밖으로 나왔을 때 만약 s가 빈 문자열이면 짝지어 제거하기가 성공적으로 이루어진 것이다.
• while문 밖으로 나왔을 때 s가 빈 문자열이 아니면 짝지어 제거하기가 실패한 것이다.

⌨ 코드1(틀린 코드)

• 시간 복잡도가 O(n^2)라서 효율성 테스트에서 통과하지 못했다.
  예) s가 'ababaababa'라 하면, 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

---

📝 풀이 과정2

• 스택을 사용한다. ('질문하기'에서 발견한 풀이방법🥺)
• 문자열에 있는 문자들을 하나씩 순회한다.
  1. 만약 stack이 비어있다면 현재 문자를 stack에 push,
     stack이 비어있지 않다면 현재 문자와 stack top을 비교한다.
  2. 현재 문자와 stack top에 있는 문자가 같다면 알파벳이 연속됨을 의미하므로 stack top을 pop한다.
     같지 않다면 stack에 현재 문자를 push
• stack에 문자가 남아있는지 검사한다.
  1. stack이 비어있다면 짝지어 제거하기 성공
     비어있지 않다면 짝지어 제거하기 실패

⌨ 코드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