mingssssss

1. 문제

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

2. 코드

from collections import deque

def solution(s):
    s = deque(s)
    check_list = deque()

    for i in range(len(s)):
        if not check_list:
            check_list.append(s.popleft())
        elif check_list[-1] == s[0]:
            check_list.pop()
            s.popleft()
        else:
            check_list.append(s.popleft())
            
    if check_list:
        return 0
    return 1

3. 리뷰

역시 효율성 테스트가 문제였다. O(n)의 연산이 넘어가면 효율성 테스트를 통과하지 못 하므로 코드의 수정이나 라이브러리가 필요한 상황이었다. 그동안 사용해야지 하면서 사용하지 못 한 deque를 사용했다. 역시나 빠르고 간편했다. bfs에서도 사용해야 하므로 친숙해지려고 노력했다. 리스트를 deaque로 만들고, chech_list가 비어있다면 s 리스트에서 popleft()를 하여 리스트를 채우고, s의 맨 앞의 원소와 check_list의 맨 뒤의 리스트를 비교하여, 같으면 지우고, 그렇지 않다면 check_list에 원소를 추가하는 식으로 진행했다.