프로그래머스 짝지어 제거하기(Python)

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

코딩테스트 연습 - 짝지어 제거하기

이 문제는 시간 초과 때문에 조금 생각을 했던 문제였다. '질문하기' 탭에서 스택이라는 단어를 언뜻 보고 난 후 깨달음을 얻어 스택을 이용해 풀었더니 바로 해결되었다.

나의 풀이

스택을 이용해 풀어야겠다 생각을 하고서 생각해낸 풀이 과정은 다음과 같다.

1. 처음에 비어있는 스택을 선언한다.
2. 문자열의 알파벳들을 하나씩 스택에 추가한다.
3. 스택에 항목을 추가할 때마다 스택에 항목들이 최소 2개가 있으며 스택의 top 포인터가 가리키는 값과 그 전 값이 같은지 확인하고 같으면 두 항목을 제거한다.
4. 마지막에 스택의 길이를 보고 결과를 판정한다.

풀이 과정을 코드로 쓰면 아래와 같다.

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

프로그래머스 효율성 테스트 채점 결과 최대 276.02ms가 걸렸고, 최대 16.4MB를 사용했다.

 

질문하기 탭을 보지 않았더라면 아마 스택을 생각해내지 못했을 것이다.. 아직 문제 풀이 경험이 부족해서 곧바로 생각나지 않는 것 같다. 좀 더 많이 풀어보자!