Lv2 짝지어 제거하기 (파이썬)

 

문제 설명

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

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

b aa baa → bb aa → aa →

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

제한사항

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

문제 풀이

문제를 처음 보고나선, "음..이건 그럼 각 문자열을 돌리면서 중복되는거 있으면 지우고 다시 업데이트 하고 다시 지우고..막 그러는건가?" 라는 생각으로 무작정 문자열을 지우려고 했었다. 그러나. 하면 할수록 이건 너무 비효율적이라는 생각이 들었다. 그리고 질문하기 서핑을 했다.

그러다 어느 힌트를 받았다. 문자열을 스택에 하나씩 넣고, 두개가 맞으면 빼고, 아니면 계속 추가하고를 반복하면 되지 않을까? 생각을 도출할 수 있었다.

 

따라서 스택의 모든 일이 끝나고 길이가 0일 경우에는 모든 짝이 맞았다는 소리고, 길이가 0 이상일 경우엔 뭔가가 남아서 짝을 이루지 못했다라는 소리이니 자연스레 0을 출력하게 하면 된다.

 

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

이 문제도 생각보다 어렵지는 않았다. 스택이라는 것을 생각하기 전까지는 많이 어려웠다고 할 수 있지만.. 구현 문제에서 이렇게 자료구조 성격의 문제들이 자주 나올듯 싶다 항상 이렇게 생각하는 사고를 길러야 할 것 같다.