[프로그래머스/python] 코딩테스트 연습 Lv.2 짝지어 제거하기

문제

 

 

입출력 예

 

 

실패 (시간초과)

def solution(s):
    s = list(s)
    tmp = s[:]
    while True:
        for i in range(1, len(s)):
            if s[i-1] == s[i]:
                del s[i-1:i+1]
                break
        if len(s) == 0:
            return 1
        elif tmp == s:
            return 0

 

이중 반복문 때문인 것 같다.

 

Solution

def solution(s):
    comp = []
    
    for i in s:
        if len(comp)==0:
            comp.append(i)
        elif comp[-1]==i:
            comp.pop()   
        else:
            comp.append(i)
    
    if len(comp)==0:
        return 1
    else:
        return 0

 

stack 개념을 이용하여 푼다.

 

ex) baabaa

순서	비교	comp = []
1	X	b
2	b != a	ba
3	a == a	b
4	b == b	X
5	X	a
6	a == a	X

 

len(comp) == 0 -> return 1