문제
문자열에서 인접한 두 개의 동일한 문자를 모두 제거합니다.
이 과정을 반복하여 문자열을 가능한 한 축소합니다.
만약 모든 문자가 제거되어 빈 문자열이 된다면 "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
Given a string, repeatedly remove adjacent pairs of matching characters and then print the reduced result.
www.hackerrank.com
'Programming > CodingTest' 카테고리의 다른 글
| [Data]Web log에서 유저별 페이지 방문 통계 (0) | 2024.10.03 |
|---|---|
| [Data] Excel 파일에서 IP 주소별 금액 집계 (0) | 2024.10.01 |
| [HackerRank] Marc's Cakewalk (마크케이크웍) Greedy 문제 (0) | 2024.08.25 |
| [HackerRank] Gemstones (잼스톤) Strings 문제 (0) | 2024.08.21 |
| [HackerRank] Caesar Cipher (시저암호) Strings 문제 (0) | 2024.08.18 |