[프로그래머스 스택/큐]짝 지어 제거하기 - Python3

문제

문자열이 주어질 때, 문자열 안에 같은 문자가 2번 나오면 제거하고, 모든 문자가 제거된다면 1을, 그렇지 않고 남는 문자가 있다면 0을 출력하는 알고리즘을 만들어라.

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

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스

 

입력

문자열

 

출력

연속된 2개의 문자를 모두 제거함으로써, 문자열의 모든 문자를 제거할 수 있는지 여부. 가능하다면 1, 아니라면 0

 

알고리즘

def solution(s):
    # 결과 값
    answer = 0
    # 문제 해결을 위한 자료구조로 스택을 선택
    stack = []

    for i in range(len(s)):
        # 스택에 문자열의 문자를 하나씩 집어넣는다.
        stack.append(s[i])

        # 스택에 문자가 1개 이하로 남아있다면, 별 다른 행동을 하지 않고 넘어간다.
        if len(stack) < 2:
            continue

        # 스택에 2개 이상의 문자가 있고, 스택의 가장 위에 있는 데이터 2개가 서로 같다면 그 2개를 없앤다.
        elif stack[-1] == stack[-2]:
            stack.pop()
            stack.pop()

    # 반복이 끝난 후, stack의 길이가 0이면 문자가 모두 제거된 것이므로 1을 리턴한다.
    if len(stack) == 0:
        answer = 1

    # 그렇지 않다면 문자가 남아있는 것이므로 0을 리턴한다.
    else:
        answer = 0
    return answer

s = "baabaa"
print("결과: ", solution(s))

 

설명

1. 파라미터로 받은 문자열을, list형의 stack배열에 하나씩 append한다. 이 stack배열은 list형이지만, 자료구조 중 스택의 형태로 다룰 것이다(파이썬의 list는 push, pop등의 메소드를 제공하므로 이 메소드를 구현하지는 않는다).

2. stack의 원소의 갯수가 1개 이하라면 별다른 동작을 하지 않고, 다시 다음 문자를 append한다.

3. stack의 원소의 갯수가 2개 이상이라면, stack의 가장 위에(뒤에)있는 원소 2개의 값을 비교한다. 두 값이 같다면 두 값을 제거하고, 그렇지 않다면 다른 동작을 하지 않는다.

4. 반복이 끝난 후, stack에 남아있는 원소의 갯수가 0개라면 모두 제거된 것이므로, 1을 출력한다. 그렇지 않을 경우, 0을 출력한다.

 

결과

원하는 값을 출력한다.

후기

스택 자료구조에 대한 이해가 필요한 문제였다. 많은 경험은 아니지만, 알고리즘 문제를 몇번 풀어보니 이번 문제에서는 스택을 사용하면 될 거라는 확신이 바로 왔다. 이런 문제는 나오더라도 아주 쉬운 문제로 나올 것 같다. 따라서, 이런 문제에서 시간을 많이 쓰지 말고 후다닥 풀어서 뒤에 문제를 풀 수 있도록 시간을 아껴야겠다. 스택의 push, pop의 진행에 따른 그림도 그리고 싶었지만, 알고리즘 공부를 하는 사람이라면 대부분 그정도는 알고 있을 것이라 생각하여 생략하였다.