[Python] SW Expert Academy - 4873. 반복 문자 지우기

SW Expert Academy 4873번 반복 문자 지우기 문제는 문자열에서 반복되는 연속 문자를 지우고 지워진 부분은 다시 앞 뒤를 연결하는데, 연결에 의해 또 반복 문자가 생기면 다시 지우고 남은 문자열의 길이를 구하는 문제이다. 스택 자료구조에 관한 문제로 난이도는 D2다.

 

SW Expert Academy 4873번 반복 문자 지우기 문제 정보

자료구조 분류

- 스택 stack

난이도

- D2

 

반복 문자 지우기 문제 요약

• 문자열에서 반복된 연속 문자 2개를 지우고, 지워진 부분을 다시 연결하는데, 만약 연결에 의해 또 반복 문자가 생기면 다시 지우기를 반복할 때 남은 문자열의 길이를 출력한다.
• 문자열의 길이는 1000 이내이다.

문제 풀이 과정

• 문자열이 끝날 때까지 문자를 하나씩 스택에 push 하고,
• 스택에 문자가 2개 이상이면 top과 top-1의 문자를 비교하여 같으면 두 문자를 스택에서 pop 한다.
• 반복문이 종료되면 남은 문자열의 길이(스택의 길이)를 리턴한다.
• 테스트 케이스 번호, 남은 문자열의 길이를 출력한다.

코드 및 설명

• stack [] - 문자열을 문자 단위로 저장하여 반복 문자를 검사하기 위한 스택 리스트
• top - 스택의 top 위치 index

def erase_repetition(str):
    stack = []
    for s in str:
        stack.append(s)
        top = len(stack) - 1
        if top > 0:
            if stack[top] == stack[top - 1]:
                del stack[top - 1:]
    return len(stack)

for t in range(int(input())):
    print("#%d %d" % (t + 1, erase_repetition(input())))

---

SWEA SW Expert Academy 4873번 반복 문자 지우기 문제는 스택 자료구조의 기본 개념을 활용한 문제로 파이썬을 사용하여 구현했다. 난이도는 D2인만큼 쉽게 풀었다.