[programmers] Level 2 짝지어 제거하기.py

프로그래머스 Level 2 짝지어 제거하기를 파이썬을 통해 풀어보았다. 

 

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

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

짝지어 제거하기.py

tomy9729/Algorithm

Level 2 짝지어 제거하기

같은 알파벳이 붙어 있을 때 제거해나가며 문자열이 완전히 제거되면 1을, 제거되지 않으면 0을 반환해야 한다. 이중 반복문을 통해 모든 문자열을 확인하며 제거할 수도 있지만 시간이 너무 오래 걸려서 효용성 테스트를 전혀 통과하지 못한다. stack을 통해 O(n)으로 문제를 풀 수 있다.

 

우선 문자열의 길이가 홀수라면 무조건 0을 반환한다. 최대한 짝지어서 제거하더라고 결국 문자열이 1개 남기 때문에 완전히 제거할 수 없다. 

 

스택을 선언한다. 문자열의 첫 번째 문자를 우선 스택에 삽입한다. 다음 문자열을 순차대로 확인한다. 만약 스택의 가장 마지막 문자와 같은 문자라면 스택에서 마지막 문자를 삭제한다. 스택의 마지막 문자와 다른 문자라면 새로 스택에 삽입한다. 이 방법을 통해 O(n) 시간 동안 짝지어 제거하기가 가능하다. "baabaa"를 보자.

 

• 현재 스택에는 아무것도 존재하지 않는다. "baabaa"의 첫 번째 문자인 b를 삽입한다. // stack = [b]
• 다음 문자인 a를 확인한다. stack의 마지막 문자와 다르기 때문에 stack에 삽입한다. // stack = [b,a]
• 다음 문자인 a를 확인한다. stack의 마지막 문자와 같으므로 stack에서 마지막 문자를 삭제한다. // stack = [b]

즉 stack에서 마지막 문자를 삭제한다는 것은 문자열에서 짝지어 제거하는 것과 같은 결과를 낼 수 있다. stack에 삽입되는 문자는 짝지어 제거되지 못하는 문자이며 stack에서 삭제되는 것은 해당 문자가 문자열에서 짝지어 제거됐다고 할 수 있다.  

• 다음 문자인 b를 확인한다. stack의 마지막 문자와 같으므로 stack에서 마지막 문자를 삭제한다. // stack = []

"baabaa"에서 앞에 있는 "aa"가 삭제되어 "bbaa"가 되었다. 이 경우 "bb"도 붙어 있게 되므로 짝지어 제거할 수 있다. stack에서 a가 삭제되면서 stack에 있는 b와 문자열의 b가 동일하므로 붙어 있는 것과 같은 상태라고 볼 수 있다. 

#Level 2 짝지어 제거하기.py
def solution(s):
    stack = []
    
    if len(s)%2 == 1 :
        return 0
    
    for i in s :
        if len(stack) == 0 : 
            stack.append(i)
        elif stack[-1] == i : 
            stack.pop()
        elif stack[-1] != i : 
            stack.append(i)
    if len(stack) == 0 : 
        return 1
    else : 
        return 0