프로그래머스 짝지어 제거하기(lv2, python)

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

문제 접근

해당 조건에 의거하여 문자열을 모두 제거할 수 있으면 1 아니면 0을 리턴하는 함수를 구현하는 문제

 

아이디어

• 문자열의 길이가 10^6이므로 O(n+@)정도의 시간복잡도로 해결하면 될듯
• 이중 for문으로 하나하나 완전탐색해줄까 했지만 구현도 복잡하고 시간복잡도상 불가능함
• 이전의 문자와 다음 문자를 비교한다는 점에서 올바른 괄호 문제와 비슷하다고 판단-> 스택을 활용
• 문자열을 스택에 넣어서 같은 문자가 나오면 제거하는 형식으로 구현

 

정답 코드

def solution(s):
    if len(s) % 2 !=0:
        return 0
    stack = []
    
    for i in range(len(s)):
        if len(stack) == 0 or stack[-1] != s[i]:
            stack.append(s[i])
        elif s[i] == stack[-1]:
            stack.pop()
            

    
    
    return 1 if len(stack) == 0 else 0