[HackerRank] SuperReducedString (같은문자열제거) Strings 문제

 

문제

문자열에서 인접한 두 개의 동일한 문자를 모두 제거합니다. 

이 과정을 반복하여 문자열을 가능한 한 축소합니다. 

만약 모든 문자가 제거되어 빈 문자열이 된다면 "Empty String"을 출력합니다.

 

예시

입력: "aaabccddd"

출력: "abd"

 

설명:

• 처음 문자열: aaabccddd
• aa 제거: abccddd
• cc 제거: abddd
• dd 제거: ab
• 최종적으로 남은 문자열: ab

 

 

풀이

string문제지만 stack을 통해 해결 할 수 있다.

문자열을 순회하면서 문자를 하나씩 처리하고, 스택의 최상단 문자가 현재 문자와 같으면 스택에서 제거하는 방식이다.

def super_reduced_string(s):
    stack = []
    
    # 문자열의 각 문자에 대해 반복
    for char in s:
        # 스택이 비어 있지 않고 스택의 최상단 문자가 현재 문자와 같다면 제거
        if stack and stack[-1] == char:
            stack.pop()
        else:
            # 스택이 비어 있거나 스택의 최상단 문자가 현재 문자와 다르면 추가
            stack.append(char)
    
    # 스택이 비어 있으면 빈 문자열을 반환, 아니면 스택의 내용을 문자열로 반환
    if not stack:
        return "Empty String"
    else:
        return ''.join(stack)

# 샘플 사용 예제
if __name__ == "__main__":
    s = "aaabccddd"
    print(super_reduced_string(s))  # 출력: "abd"

 

중간 변수의 상태

문자열 순회:

• 문자 'a': 스택이 빈 상태이므로 ['a']
• 문자 'a': 스택의 최상단이 'a'이므로 제거 -> []
• 문자 'a': 스택이 빈 상태이므로 ['a']
• 문자 'b': 스택이 비어 있거나 최상단과 다르므로 ['a', 'b']
• 문자 'c': 스택의 최상단이 'b'와 다르므로 ['a', 'b', 'c']
• 문자 'c': 스택의 최상단이 'c'이므로 제거 -> ['a', 'b']
• 문자 'd': 스택의 최상단이 'b'와 다르므로 ['a', 'b', 'd']
• 문자 'd': 스택의 최상단이 'd'이므로 제거 -> ['a', 'b']
• 문자 'd': 스택의 최상단이 'b'와 다르므로 ['a', 'b', 'd']

최종 상태: ['a', 'b'] → 'ab'

 

 

 

https://www.hackerrank.com/challenges/reduced-string/problem?isFullScreen=true

Super Reduced String | HackerRank