[PCCP] 스택(Stack) - 연속된 문자 지우기 | 파이썬

코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

스택(Stack) - 연속된 문자 지우기

앞서 공부한 스택을 사용해 연속된 문자 지우기 문제를 풀어보겠다.

---

문제

매개변수 s에 문자열이 주어지면 이웃한 두 개의 문자가 같으면 두 문자를 제거합니다.
이 과정을 반복해서 최종적으로 남는 문자만으로 이루어진 문자열을 반환하는 프로그램을 작성하세요.
만약 "acbbcaa"라는 문자열이 주어진다면 최초 bb가 연속되어 있어 제거하고 나면 "accaa"가 되고, 다시 cc가 연속되어 제거하면 "aaa"가 되고 "aa"연속되어 제거하면 "a"가 최종적으로 남습니다.

---

입출력 예

s	answer
"acbbcaa"	"a"
"bacccaba"	"bacaba"
"aabaababbaa"	"a"
"bcaacccbaabccabbaa"	"ba"
"cacaabbc"	"ca"

---

제한사항

• 문자열 s의 길이는 100,000을 넘지 않습니다.
• 문자열 s는 소문자로만 이루어져 있습니다.

---

코드

def solution(s):
    stack = []

    for char in s:
        if len(stack) > 0 and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)

    return "".join(stack)

print(solution("acbbcaa"))
print(solution("bacccaba"))
print(solution("aabaababbaa"))
print(solution("bcaacccbaabccabbaa"))
print(solution("cacaabbc"))

---

풀이

1. s에서 문자를 하나 받아 만약 stack이 비어있지 않고, stack의 마지막 원소가 char와 같은 경우 stack에서 가장 마지막 문자 삭제
2. 위 조건을 만족하지 않는다면 char를 stack에 삽입
3. 그렇게 모든 문자를 다 돌면 join문을 이용해 stack을 return