짝지어 제거하기 (시간초과 -> 통과)

 

첫번째 방법: 시간초과 

def solution(s):
    answer = -1

    i = 0
    
    while (i<len(s)-1 and len(s)>=1):
        #print('s',s)
        cur_str = s[i]
        next_str = s[i+1]
        
        if cur_str == next_str:
            s = s[:i] + s[i+2:]
            #print('new_s',s, 'new_s',len(s))
            i = 0
        
        else:
            i += 1
    if len(s) == 0:
        answer = 1
    else:
        answer = 0
    
    return answer

 

두번째 방법: stack 으로 접근

 

 

(차이점은?) stack 으로 O(N)으로 해결 

q 길이 신경쓰는거 때문에 시간이 좀 더 들었다.

from collections import deque

def solution(s):
    answer = -1
    
    # stack_l = []
    q = deque()
    q.append(s[0])
    
    for s_item in s[1:]:
        if len(q)>=1:
            if q[-1] == s_item:
                q.pop()
            else:
                q.append(s_item)
        else:
            q.append(s_item)
    
    if len(q)== 0:
        answer  = 1
    else:
        answer = 0
    
    
    return answer