리트코드 2390. Removing Stars From a String

https://leetcode.com/problems/removing-stars-from-a-string/description/?envType=study-plan-v2&envId=leetcode-75

별 *이 포함된 문자열 s가 주어진다.

한 번의 operation으로 다음이 가능하다:

1. s에서 별을 선택합니다.
2. 왼쪽에서 가장 가까운 별이 아닌 문자를 제거하고 별 자체도 제거한다.

모든 별이 제거된 후의 문자열을 반환한다.

 

풀이 1 - 스택을 활용한 풀이

1. 살아남은 문자열을 보관하기 위한 스택을 생성한다
2. 문자열을 순회하면서 다음과 같이 확인한다.
   1. 스택이 비어있거나, 문자열이 별이 아니라면, 스택에 추가한다.
   2. 그렇지 않으면 스택에 있던 마지막 문자열을 제거한다.

이 과정을 거치면 문자열 순회가 종료되고 별 제거 연산이 끝난 문자열이 반환된다.

 

class Solution:
    def removeStars(self, s: str) -> str:
        stk = []

        for c in s: # O(n)
            if not stk or c is not "*": # O(1)
                stk.append(c) # O(1)
            else:
                stk.pop() # O(1)

        return "".join(stk) # O(n)

 

시간 복잡도 : 문자열을 순회하면서 stk의 마지막 문자를 처리하기 때문에 O(n)의 시간복잡도를 가진다.

공간 복잡도 : 스택 배열을 생성하므로 O(n)의 공간복잡도를 가진다.

 

풀이 2 : 문자열 그대로를 활용한 풀이

1. 추가적인 배열을 생성하지 않고 입력 문자열을 그대로 활용할 풀이도 가능하다.

2. 파이썬의 문자열은 immutable하기 때문에 list로 변환한다. - 이는 공간복잡도 산정에서 제외한다.

3. 변환된 문자열을 갱신하기 위한 포인터 인덱스 write를 생성한다. - rea

4. 입력 문자열을 순회하면서 - read 포인터 인덱스. *이 아닐경우에는 write 인덱스에 해당되는 문자열을 read 인덱스에 해당되는 문자열로 교체한다. 그리고 write 인덱스를 + 1 한다.

5. 만약 *일 경우에는 왼쪽 인접 문자열을 제거해야 하므로, write 인덱스를 - 1 한다. 이렇게 되면 다음 반복문에서 read 포인터 인덱스가 *이 아닐경우 해당 문자열로 교체되게 될 것이다.

6. 연산을 모두 종료한 이후 write 포인터까지 문자열을 반환하면 최종적으로 변환된 문자열을 확인할 수 있다.

 

class Solution:
    def removeStars(self, s: str) -> str:
        chars = list(s) # O(1)
        write = 0

        for read in range(len(chars)): # O(n)
            if chars[read] != "*": # O(1)
                chars[write] = chars[read] # O(1)
                write += 1
            else:
                write -= 1
        
        return "".join(chars[:write]) # O(n)

 

시간 복잡도 : 문자열을 한 번 순회하므로 시간 복잡도는 O(n)이다.

공간 복잡도 : 추가적인 자료구조를 생성하지 않으므로 (문제 풀이 특성 상 부득이한 배열 변환은 제외) 공간 복잡도는 O(1)이다.