[Programmers] 짝지어 제거하기

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

개요

문제를 처음 봤을 때 Stack의 괄호 짝 맞추기가 생각났다. 풀이과정에서 문자열을 복사하는 방법도 생각해보고 hashmap도 사용해보는 게 어떨까 싶었지만 풀이 순서를 세우고 보니 Stack이 과정 적합한 자료구조라 판단했다.

Solve

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, value):
        self.stack.append(value)

    def pop(self):
        self.stack.pop()

    def top(self):
        try:
            return self.stack[-1]
        except IndexError:
            return None


def solution(s):
    stack = Stack()

    stack.push(s[0]) 

    for ch in s[1::]:
        if stack.top() != ch:
            stack.push(ch)
        else:
            if stack.top() == ch:
                stack.pop()

    if len(stack.stack) == 0:
        return 1
    else:
        return 0

문자열을 제거해나가는 핵심 로직을 다음과 같이 계획하고 풀어나갔다.

1. Stack에 저장하기전 저장된 문자열이 존재하는지 체크
   1. 저장된 문자가 없다면 저장한다
   2.  저장된 문자가 있다면 기존에 저장된 문자를 제거한다.
2. Stack에 문자가 남아있다면 0을 Stack에 문자가 없다면 1을 리턴한다.
   
   

효율성 부분을 보니 뭔가 간당간당하게 풀리지 않았나 싶은 생각이 든다. 다른 사람들은 어떻게 풀었는지 체크해보자.