[프로그래머스] Lv2 - 짝지어 제거하기 (파이썬)

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

코딩테스트 연습 - 짝지어 제거하기

 

def solution(s):
    answer = 0 if can_remove(s) else 1
    return answer


def can_remove(s):
    stack = []
    for x in s:
        if not stack:
            stack.append(x)
        else:
            if stack[-1] == x:
                stack.pop()
            else:
                stack.append(x)
    return stack

 

자료구조, 스택
1. can_remove() : 문자열을 제거하고 남은 문자열 리스트 반환
    - 스택을 이용
    - 스택에 append를 해나가다가 stack의 top과 넣을 문자가 같으면 pop 아니면 append
    - stack 반환
2. stack에 값이 있다면 불가능 : 0 리턴, 비어 있다면 가능 : 1 리턴

 

N은 최대 1,000,000이다. 이를 2중 반복문을 이용하면 시간 초과

시간 복잡도를 고려, stack을 이용하여 O(N)으로 풀 수 있다.