[ 프로그래머스 ] LV.2 짝지어 제거하기

 

// 문제요약

 

문자열 s 가 주어지면 짝이 맞는 문자 한 쌍을 제거하고

 

앞뒤로 남은 문자들을 다시 붙이는 작업을 반복할때

 

모든 문자를 없앨 수 있다면 1 그렇지 않다면 0을 반환하는

 

함수를 완성해라.

 

// 사고

 

특정한 페턴을 추출/제거하는 방식중에서 

 

stack의 선입후출 LIFO의 특성을 이용하는 전형적인 문제다.

 

이미지 가져온곳 : https://www.reddit.com/r/Accounting/comments/k3lzwk/fifo_vs_lifo/

 

보여지는 대로...

 

선입선출은 먼저 들어간 것이 먼저 나오는 것이고

 

선입후출은 먼저 들어간 것이 나중에 나오는 것이다.

 

편의점 알바를 해보면 저 둘의 차이를 확실히 알것이다.

 

사장님은 선입선출로 정리하라고 하고 손님들은 선입후출로 사가려고 한다...

 

아무튼 문제를 많이 풀어보면 어느 순간 자동으로 스택이라는 것을 직감하게 되는 전형적인 문제다.

 

페턴을 외워두는 것도 나쁘지 않다.

 

 

// 풀이

 

원래는 선입선출/후출을 queue와 stack으로 구분하여 사용하지만

 

파이썬에서는 이런 구분으로 나누어 사용하지 않고

 

list의 append()와 pop()이라는 메소드를 이용하여 stack 연산을 구현할 수 있다.

 

참고하여 아래의 코드를 보자.

 

def solution(s):

    # 가장 최근에 탐색된 대상과 비교해야하므로
    # 선입후출 식으로 비교되어야 한다.
    # 모든 비교를 마치고 stack에 아무것도 남아있지 않다면
    # 모든 문자가 짝을 이룬다는 의미이므로 1을 반환하고
    # 그렇지 않다면 0을 반환한다.
    # 전형적인 stack 문제라고 할 수 있다.

    stack = [] # stack을 만든다.
    for char in s:
        # 받은 문자열에서 문자를 하나씩 꺼낸다.
        if stack and stack[-1] == char:
            stack.pop()
            # 만약 stack에 원소가 하나라도 있고
            # 그중 가장 마지막에 추가된 원소가 추출된 문자와 같으면
            # 스택의 마지막 문자를 버린다.
            # 그리고 아무런 작업도 하지 않으므로 char도 버려진다.
        else:
            stack.append(char)
            # 그렇지 않다면 char를 stack에 추가하여 다음 char 와 비교한다.

    if stack:
        return 0
        # 모든 비교가 끝났는데도 stack에 문자가 남아있다면 0을 리턴한다.
    else:
        return 1
        # 모든 비교가 끝났을때 stack에 아무것도 남아있지 않다면 1을 리턴한다.

풀이 끝