프로그래머스 - 짝지어 제거하기

문제 이해

입력값으로 들어온 문자열 중 인접한 두 글자씩 짝지어 제거하는 문제

해당 문제를 봤을 때 그냥 계속 포문으로 반복 검사한다면 O(n^2)이 나올 수 있기 때문에 주의해야 한다.

 

따라서 이 문제를 더 효율적으로 풀기 위해서는 다른 방법을 생각해볼 필요가 있는데

스택을 이용하면 쉽고 빠르게 해결할 수 있다.

 

for문으로 문자열을 이터레이션하며 스택의 top과 비교하며 다음과 같은 로직을 수행한다.

같을 경우 : 스택에 pop()
다를 경우 : 스택에 push() -> 파이썬 list에서는 append()를 이용

다음과 같이 구현할 경우 문자열 길이만큼 이터레이션 하기 때문에 O(n)으로 풀이할 수 있으며

해당 로직이 끝난 후 스택에 데이터가 남아있는지를 체크해 1, 0을 알맞게 넣어주면 된다.

 

해답

def solution(s):
    stack = []
    
    for c in s:
        if len(stack) == 0:
            stack.append(c)
            continue
            
        top = stack[-1]
        if c == top:
            stack.pop()
        else:
            stack.append(c)
            
    if stack:
        answer = 0
    else:
        answer = 1

    return answer