반복문자 지우기 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4873

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVHzyqqe8DFAWg

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

문자열 s에서 반복된 문자를 지우려고 한다. 지워진 부분은 다시 앞뒤를 연결하는데, 만약 연결에 의해 또 반복문자가 생기면 이부분을 다시 지운다. 반복문자를 지운 후 남은 문자열의 길이를 출력 하시오. 남은 문자열이 없으면 0을 출력한다.   다음은 CAAABBA에서 반복문자를 지우는 경우의 예이다.   CAAABBA 연속 문자 AA를 지우고 C와 A를 잇는다. CABBA 연속 문자 BB를 지우고 A와 A를 잇는다. CAA 연속 문자 AA를 지운다. C 1글자가 남았으므로 1을 리턴한다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤ 50   다음 줄부터 테스트 케이스의 별로 길이가 1000이내인 문자열이 주어진다.

출력

#과 1번부터인 테스트케이스 번호, 빈칸에 이어 답을 출력한다.

예시

입력	출력
3 ABCCB NNNASBBSNV UKJWHGGHNFTCRRCTWLALX	#1 1 #2 4 #3 11

---

2. 문제풀이

파이썬 스택 1일차 연습문제 중 하나인 반복문자 지우기 문제이다. 같은 문자가 나올경우 두개의 문자를 지우는 문제인데 스택을 이용하면 O(N)만큼만으로 풀수가 있게된다. 스택에 데이터를 넣는것을 기초로 하는데 넣기전에 스택의 탑부분을 확인하게 된다. 만약 스택의 탑부분과 같다면 pop을 하여 데이터를 제거한다. 탑부분과 다르다면 스택에 push를 한다. 마지막까지 작업을 했을경우, 스택의 남은 길이만큼 출력을 하면 된다.

---

3. 소스코드

for t in range(int(input())):
    user_input = input()
    stack = []
    for s in user_input:
        if len(stack) == 0:
            stack.append(s)
        else:
            if s == stack[-1]:
                stack.pop()
            else:
                stack.append(s)
    print('#{} {}'.format(t+1, len(stack)))