[Python] 프로그래머스 12973. 짝지어 제거하기 (Lv.1)

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

프로그래머스

문제에서 요구한 그대로 구현하면 쉽게 풀릴 것 같지만, 입력 문자열의 길이가 100만이기 때문에 좀 더 효율인 방법이 필요합니다. 

 

예를 들어 입력이 10일때 요구한 그대로 문자열을 비교한다면 알파벳이 2개씩 사라지므로 5번의 시행이 필요하고 그 때마다 10, 8, 6, 4, 2 길이의 문자열을 자르고 이어붙여야합니다. 문자열의 길이가 길수록 기하급수적으로 커지겠죠.

 

Stack, 혹은 List 등의 자료구조를 활용하여 맨 뒤의 알파벳만 비교할 수 있습니다. 이 경우엔 정확히 문자열의 길이만큼만 다루면 됩니다. Python 기준으로 List를 Stack과 유사하게 사용할 수 있으므로 이를 사용해 알파벳을 넣어주고, 만약 맨 뒤의 알파벳(즉 나와 맞닿은 알파벳)이 같다면 지워주는 식으로 풀 수 있습니다.

 

def solution(s):
    st = []
    
    for c in s:
        if len(st) > 0 and st[-1] == c:
            st.pop()
        else:
            st.append(c)
    
    return 1 if len(st) == 0 else 0