영어 대소문자로 이루어진 문자열 s가 있다고 가정해 보겠습니다. 이때 다음 조건에 해당하는 인접한 두 문자 s[i]와 s[i+1]의 쌍이 하나도 없는 문자열을 '좋은 문자열(good string)'이라고 정의합니다.
- 0 <= i <= len(s) - 2
- s[i]가 소문자이고 s[i+1]이 같은 글자의 대문자인 경우, 또는 그 반대의 경우
문자열을 좋은 문자열로 만들려면, 문자열을 '나쁘게' 만드는 인접한 두 문자를 골라 제거하면 됩니다. 이 과정을 문자열이 좋은 문자열이 될 때까지 반복합니다(빈 문자열 역시 좋은 문자열로 간주합니다). 최종적으로 변환된 문자열을 구하는 것이 목표입니다.
예를 들어 입력이 s = "popPpulaBbr"라면 출력은 "popular"가 됩니다. 먼저 "pP"(또는 "Pp")를 제거한 뒤, 이어서 "Bb"를 제거하기 때문입니다.
해결 접근 방법
이 문제는 스택(stack) 개념을 활용하면 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 결과를 저장할 새 리스트 res를 생성합니다.
- 문자열 s의 각 문자 ch에 대해 다음을 반복합니다.
- res가 비어 있지 않고, res의 마지막 원소가 ch와 대소문자 관계없이 같은 글자라면 res의 마지막 원소를 삭제(pop)합니다.
- 그렇지 않으면 ch를 res의 끝에 추가(append)합니다.
- res의 모든 원소를 이어 붙여(join) 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(n)으로, 문자열을 한 번만 순회하면서 효율적으로 처리할 수 있습니다.
파이썬 구현 예시
다음 코드를 통해 더 잘 이해해 보겠습니다.
def solve(s):
res = []
for ch in s:
if res and res[-1] != ch and res[-1].lower() == ch.lower():
res.pop()
else:
res.append(ch)
return ''.join(res)
s = "popPpulaBbr"
print(solve(s))입력
"popPpulaBbr"출력
popular코드에서 핵심 조건은 res[-1] != ch and res[-1].lower() == ch.lower()입니다. 즉, 두 문자가 실제로는 다르지만 소문자로 변환했을 때 동일하다면 서로 대소문자만 다른 같은 글자이므로, 스택에서 마지막 문자를 제거해 해당 쌍을 없애는 방식입니다.