짝지어 제거하기

문제풀이

효율성 실패

처음 문제를 해결한 솔루션은 하드코딩적인 방법을 사용했다. 문제 그대로 같은 부분을 발견하면 문자열에서 잘라내고 그 전부터 다시 검사하는 방식을 사용했다. 하지만 이는 효율성에서 점수를 받지 못했다.

효율성 반 성공

역시 위의 효율성 실패는 알고리즘을 제대로 활용하지 못한 점에 있다.  따라서 어떤 알고리즘을 사용해야 적절한 지 고민해본 결과 stack이 좋다고 판단했다. 하지만 stack을 활용하긴 했지만 심플한 솔루션을 내지 못했다.

효율성 해결

def solution(s):
    answer = 0
    
    s = list(s)
    stack = []
    for word in s:
        if stack:
            if stack[-1] == word:
                stack.pop()
            else:
                stack.append(word)
        else:
            stack.append(word)
    if len(stack) == 0:
        answer = 1        
        
    return answer

내가 효율성을 실패한 원인은 주어진 s의 짝지어진 문자도 삭제하려고 했기 때문이다. 또 stack은 짝지어지지 않은 문자만 넣으려 했던 것도 문제 해결을 복잡하게 만들었다.

stack에 문자가 없으면 s에서 문자를 하나 넣고, stack에 문자가 있으면 이를 s의 문자와 비교한 뒤 같으면 stack의 문자를 지우고 그렇지 않을 경우 stack에 문자를 추가한다. 

출처

문제: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

파이썬 자료구조와 알고리즘 - 미아 스타인 저/최길우 역