[Python/파이썬] 프로그래머스 짝지어 제거하기

프로그래머스

코드

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

입력으로 주어진 문자열 s에 대해 문자 하나씩 스택에 넣으며 비교하는데 이때 스택의 top과 같다면 같은 문자가 반복되어서 제거할 수 있는 것이므로 이 경우에는 해당 문자를 넣지 않고 스택의 top에 있던 원소도 pop으로 빼준다. 이렇게 문자열의 끝까지 탐색하고 stack에 남은 원소가 있다면 짝지어 제거하기에 실패한 것이므로 0을 리턴해주고 아니라면 성공적으로 수행한 것이므로 1을 리턴해준다.

 

처음에는 아래와 같이 풀이하였는데 이 경우 문자열을 제거하면 다시 처음부터 앞으로 돌아가 다시 비교하므로 매우 비효율적이다. 위의 코드는 문자열 전체를 1번만 탐색하지만 아래의 코드는 최대 (n * (n-2) * ... * 2)번 연산하므로 시간 초과가 뜬다.

def solution(s):
    l = len(s)
    idx = 0
    prev = s[0]
    while True:
        idx += 1
        if idx >= l:
            return 0
        if prev == s[idx]:
            if l == 2:
                return 1
            else:
                s = s[:idx-1] + s[idx+1:]
                idx = 0
                l -= 2
                prev = s[0]
        else:
            prev = s[idx]