프로그래머스 Python 문제풀이 입니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12973

[나의 풀이1]

def solution(s):
    
    answer = -1
    
    while answer == -1:
        
        len1 = len(s)
        for i in range(0,len(s)-1):
            if s[i] == s[i+1]:
                s = s.replace(s[i:i+2],"")
                break
        len2 = len(s)
        
        if len1 == len2:
            answer = 0
            break
        if s == "":
            answer = 1

    return answer

[나의 풀이2]

def solution(s):
    
    answer = -1
    
    while answer == -1:
                
        len1 = len(s)
        for i in range(0,len(s)-1):
            if s[i] == s[i+1]:
                s = s[:i] + s[i+2:]
                break
        len2 = len(s)
        
        if len1 == len2:
            answer = 0
            break
        if s == "":
            answer = 1

    return answer

문제를 정의하고 구현해내는데는 어렵지 않았습니다. 하지만 구현한 위의 두가지 풀이 모두 일부 케이스에서 시간 초과가 나서 다른 풀이를 참고하여 해결하였습니다.🐒🐒🐒

아래와 같이 stack 개념을 활용하여

[다른 사람의 풀이]

def solution(s):

    answer = -1

    stack = []

    for el in s:
        if len(stack) == 0 :
            stack.append(el)
        elif stack[-1] == el:
            stack.pop()
        else:
            stack.append(el)

    if len(stack) == 0:
        answer = 1
    else :
        answer = 0

    return answer

최초에 stack이 비어있다면 먼저 넣어주고, 다음에 오는 문자열이 같으면 제거하고 다르다면 stack 형식으로 쌓이는 방식입니다. First In Last Out 구조로 다음 바로 문자열이 동일하지 않더라도 다음 문자열과 그 다음 문자열이 동일하여 제거된다면 이전에 쌓인 문자열 또한 pop()되어 stack을 모두 비울 수 있습니다. 이번 문제를 통해서 Stack 자료구조 개념을 되짚어보고 활용하는 방식에 대해 이해할 수 있었습니다.

감사합니다.