프로그래머스

짝지어 제거하기

문제 링크

처음에는 이중 반복문을 사용하여 테스트 케이스를 통과하고 제출을 했지만

실패한 코드

def solution(s):
    length = len(s)
    for _ in range(length // 2):
        for i in range(len(s) - 1):
            if s[i] == s[i + 1]:
                s = s.replace(s[i] * 2, "")
                break

    return 0 if s else 1

처참한 결과.....

제한사항의 문자열의 길이 : 1,000,000이하의 자연수을 보고 반복문만 사용하면 안되겠다는 생각을 했고 스택을 사용해야겠다고 생각했다.

직접 써보면서 알고리즘을 생각하고 구현해보았다.

코드

def solution(s):
    stk=[]
    
    for i in s:
        if stk:
            if stk[-1]==i:
                stk.pop()
            else:
                stk.append(i)
        else:
            stk.append(i)    

    return 0 if stk else 1

반복문을 한번만 사용하고 코드도 더 깔끔해진 느낌

성공~