프로그래머스 - 짝지어 제거하기 (핵심 : int(True)로 리턴하기)

💡문제 분석 요약

• baabaa 이런 문자가 있을 때, 앞에서부터 2개씩 짝지어지면 제거한다.
• 모두 짝지어지면 1을 반환, 아니면 0을 반환한다.

💡알고리즘 설계

• 앞에서부터 stack에 하나씩 넣어주면서 체크하면 된다. sentence의 i번째와 stack의 -1번째가 같은 문자라면 삭제하는 방식이다.

💡코드

def solution(sent):
    sent = list(sent)
    stack = []
    for c in sent:

        # 스택이 비어있으면 append
        if len(stack) == 0:
            stack.append(c)
            continue

        if stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)

    return int(len(stack)==0)

print(solution("baabaa")) # 1
print(solution("cdcd")) # 0

💡시간복잡도

• sentence에 대해서만 진행하면 되므로 O(N), stack에 append하고 pop하는 것은 O(1)이다.

💡 틀린 이유, 수정

• X

💡 느낀점 or 기억할정보

• 어렵진 않았는데, 약간의 코드 팁은 return할 때 True, False형태를 1, 0으로 표현하려면 int로 감싸주면 된다는 것이다.
• 그래서 len(stack)==0 을 반환할 때 int로 감싸주면 True는 1, False는 0으로 반환한다.