[Leetcode/Python] 1047. Remove All Adjacent Duplicates In String

문제 링크

Remove All Adjacent Duplicates In String - LeetCode

 

문제 설명

 영어 소문자로 구성된 문자열 s가 제공됩니다. 이 문자열에서 두 개의 인접하고 동일한 문자를 선택하여 제거하는 것으로 구성됩니다. 이 방식은 더 이상 할 수 없을 때까지 반복적으로 중복 제거를 수행합니다.

 이러한 모든 중복 제거가 수행된 후 최종 문자열을 반환합니다. 반환된 값은 독특하다는 것을 알 수 있습니다.

 

입출력 예시

Input	Output
"abbaca"	"ca"
"azxxzy"	"ay"

 

제한 사항

• 1 <= s의 길이 <= 105
• s 는 영어 소문자로만 구성되어 있다.

문제 풀이

 처음 이 문제를 봤을 때는 한 지점을 선택해서 풀었다. 투포인터 방식에서 영감을 받아 푸는 형식인데, 머릿속으로는 시간복잡도  O(n)과 공간복잡도 O(1)을 가질거라 예측했다.

 

 이 방법의 풀이는 다음 소스코드에서 '포인터 풀이법'을 보면 된다. 입력받은 숫자에서 맨 앞부터 천천히 한글자씩 본다. 그리고 다음글자와 비교해서 같으면 해당하는 글자 두개를 빼는 식이다. 간단히 생각하면 O(n)의 시간복잡도를 가지지만, 파이썬의 리스트 컴프리핸션은 그렇지 못한듯 하다. 그래서 시간복잡도가 O(n^2)이 나왔다.

 

 그래서 다른 방식인 스택을 이용한 풀이를 해봤다. 이 경우 시간복잡도가 O(n)이 되는게 당연하지만, 새로운 한 공간을 만들어야 하기에 공간복잡도는 O(n)이 된다. 기존에는 O(1)에서 늘어났지만, 그래도 많아진편은 아니다.

소스코드

# 스택 풀이법
class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = ['']
        for i in s:
            if stack[-1] == i:
                stack.pop()
                continue
            stack.append(i)
        return "".join(stack)
        
 # 포인터 풀이법
 class Solution:
    def removeDuplicates(self, s: str) -> str:
        location = 0
        while location < len(s) - 1:
            if s[location] == s[location + 1]:
                s = s[:location] + s[location + 2:]
                if location != 0:
                    location -= 1
            else:
                location += 1
        return s

 

코딩 테스트, 어떻게 대비해야 할까?