SWEA - 반복문자 지우기 (4873) [Python]

 문제

 

- 문자열 s의 반복된 부분을 삭제한다. 연속문자를 계속 지워나간다. CAAABBA 의 경우 AA를 지워 CABBA가 되고 BB를 지워 CAA, 다시 AA를 지워 C만 남는다. 남은 길이를 출력한다.

 

 

 문제 상황

 

- 연속되는 문자를 지우는 상황으로 카카오 문제의 인형뽑기 문제와 비슷하다. 연속으로 같은 것이 있으면 지워지는 개념이다. 

 

 

 해결 전략

 

- stack을 활용해서 채워나가면서 마지막 두 값이 같은지를 확인하는 부분을 만든다.

 

 

 코드

 

T = int(input())
for idx in range(T):
    s = list(input())
    # 들어오는 문자를 확인할 스택
    stack = []
    # stack에 채울 숫자를 하나하나 확인
    for i in range(len(s)):
        # stack이 비어있지 않고 넣으려는 값이랑 같은 값이 마지막에 존재하면
        # stack의 top 값을 제거한다.
        if stack and stack[-1] == s[i]:
            stack.pop()
        # 위의 상황이 아니면 s[i]를 추가한다.
        else:
            stack.append(s[i])
    print(f"#{idx+1} {len(stack)}")
    
 

 

 

 해설

 

- 처음에는 넣은 후 index가 -1, -2 인 값을 비교해 같으면 지우는 구조를 생각했지만 그렇게 되면 쓸데없이 append하는 과정이 생기고 if 조건문이 하나 더 생기므로 속도 낭비가 생긴다. 넣는 단계에서 같으면 두개를 제거하는게 아니라 기존에 존재하는 한개만 제거하는 것이 더 효율적이다.

 

 

 새로 학습한 것 & 실수 

 

- .

 

 

출처 - https://swexpertacademy.com/main/