[Py_Lv2] 짝지어 제거하기

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한 사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

입출력 예

접근법

우선, 문제 설명을 이해 후 공부한 알고리즘 이론을 적용하는 연습이 부족하여
해당 문제를 알고리즘으로 해결하는데 많은 시간이 걸렸습니다..😂

오랜시간 읽어보고 이렇게 저렇게 시도해보니 공부한 내용 중 스택에 원리를 이용하여
풀 수 있는것으로 확인 하였습니다..

값의 비교를 위해서는 기존에 리스트에 값을 다른 리스트에 하나 하나 옮기는 과정이 필요해
stack이란 리스트를 만들었습니다.

이후 s 리스트에 값을 stack으로 이동하여 다음에 올 문자를 앞에 문자와 비교하여
같지 않을 경우 추가, 같을 경우 stack 입력된 문자를 삭제시킵니다.

이 과정에서 가장 마지막에 입력된 문자를 삭제하기 때문에 pop()을 이용합니다.

최종적으로 동일한 문자들이 연결되어 삭제가 가능한 경우라면 위 방법으로 모두 삭제되어
stack 리스트에는 아무값도 존재하지 않습니다.

이런 경우에는 1을 반환해주고 그렇지 않고 stack 리스트에 값이 존재한다면 0을 반환합니다.

def solution(s):
    answer = 0
    stack = []
    for i in s:
        if len(stack) == 0:
            stack.append(i)
        elif stack[-1] == i:
            stack.pop()
        else: 
            stack.append(i)
    if len(stack) ==0:
        solution = 1
    else:
        solution = 0
    return solution