프로그래머스 level2 _ 짝지어 제거하기 [Python]

나는 왜 틀렸는가?

우선 이런 종류의 문제는 queue, stack을 써서 풀어야한다는 생각을 떠올려야 한다.

나는 기존의 문자열에서 replace함수를 이용해 바꾸는 식으로 풀었는데, 이렇게 풀면 시간도 오래걸리고, 문자열의 인덱스번호도 계속 달라지고 무엇보다 while문의 탈출 조건도 만들기 어렵기 때문에 문제가 복잡해진다.

아래는 내가 처음 시도했던 잘못된 풀이이다.

def solution(s):
    answer = 0
    while True:
        if s == check(s):
            break
        s = check(s)
    if len(s) == 0:
        answer = 1
    return answer

def check(s):
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            s = s.replace(s[i],"",1)
            s = s.replace(s[i],"",1)
            break
    return s

정답 풀이

정답 풀이는 아래와 같다.

stack(python에서는 기본 list)을 하나 선언하고, 문자열 s에서 문자 i를 순회하며 stack에 추가하는데 이때, 제일 마지막에 추가한 문자와 현재 추가하려는 문자가 동일하면 제일 마지막에 추가한 문자를 제거한다.

for문이 끝나고 stack의 길이가 0이면 1을, 아니면 0을 반환한다.

def solution(s): 
    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: return 1
    else: return 0

마치 몇일 전 풀었던 괄호 문제와 비슷하다 ... stack과 queue .. 기억하자 !!