[알고리즘 문제 풀이] - 짝지어 제거하기

 같은 문자 두개가 붙어 있다면 제거가 되는 룰이 있네요.

 

그렇게 계속 제거를 해 나가다가 "cdcd"처럼 제거가 되지 않는 경우에는 0을 리턴하고

 

모두 제거가 되면 1을 리턴하면 되는 문제 입니다.

 

 

생각의 과정

1. 우선 입력된 문자열 s를 위한 loop이 하나 필요할것 같다.

 

2. 그 후에 안에 서로 연속된게 있는 loop을 하나 더 넣어서 nested loop을 만들까? 이러면 많이 느려질것이다.

 

3. 연속된게 2개 이상이라도 어차피 한번에 제거될수 있는 개수는 2개뿐이다. 

 

4. 그렇다면 stack을 따로 만들어서 끝자리끼리만 비교해보자

 

 

풀이

def solution(s):
    stack = []
    s_list = [ch for ch in s]
    while s_list:
        temp = s_list.pop()
        if stack:
            if stack[-1] == temp:
                stack.pop()
            else:
                stack.append(temp)
        else:
            stack.append(temp)
    return 0 if stack else 1

 

우선은 stack 구조를 쓰기 위해서 인풋 s를 리스트 안에 넣었습니다.

 

파이썬의 리스트는 스택처럼 사용 가능합니다.

 

그리고 빈 stack을 하나 생성합니다. 그리고 loop을 돌려서

 

리스트의 끝자리부터 꺼내서 연속된게 같은지 비교를 합니다.

 

while loop을 썼습니다. loop은 문자열을 넣은 리스트가 비어 있기전까지 돌아갑니다.

 

pop()은 스택의 마지막 element를 빼내는건데요. 시간복잡도가 O(1)이라서 매우 빠릅니다.

 

이렇게 리스트안에 모든 문자를 빼내서 비교하고

 

스택 안에 제거되지 않은 문자가 남아 있다면 0을 리턴하고 모두 제거 되었다면 1을 리턴합니다.

 

결과는

 

역시 효율성 테스트가 따로 있었고 통과된 시간들을 봐서는 

 

시간 제약이 타이트한 문제네요.

 

만약 while loop안에 loop이 하나 더 들어간 nested loop이었다면

 

무조건 시간 초과가 나왔을것 같습니다.

 

이렇게 시간적인 제약이 많은 문제는 stack 구조가 큰 도움이 될것 같습니다.