[99클럽 코테 스터디] 25일차 TIL - 스택/큐, Removing Stars From a String

[25일차 미들러] 스택/큐

문제: https://leetcode.com/problems/removing-stars-from-a-string/description/

* 번역: *을 포함하는 문자열 s가 주어진다. 한 동작에서 s에서 *을 하나 선택하고, 그 별의 왼쪽에서 가장 가까운 별이 아닌 문자열을 제거할 수 있다. 별 자신도 제거할 수 있다. 모든 별이 제거된 후의 문자열을 반환하라. 

입력값은 항상 연산 가능하도록 주어진다. 결과 문자열은 항상 고유하게 나타난다.

Solution

for문으로 문자열 s를 순회하면서, 스택에 문자를 추가해주는 방식으로 구현했다.

문자가 *인 경우, 스택의 맨 위 요소를 제거한다. 일반 문자인 경우, 스택에 추가한다. 이 스택에는 *이 아닌 문자열, 곧 결과만 저장되는 셈이다.

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        
        for char in s:
            if char == '*':
                if stack:
                    stack.pop()
            else:
                stack.append(char)
        
        return ''.join(stack)

나다어

나는 다음에 어떻게 할까

• 리스트를 문자열로 바꿀 때는 ''.join(리스트)
• 답을 저장하기 위한 변수를 따로 두면 문제가 간단하게 풀릴 때가 있다.

오답노트.

• while 문을 사용할 때는 종료 조건을 잘 정하는 것이 중요하다. while문과 인덱스를 사용하는 것은 for문을 사용하는 것과 비슷하므로 종료 조건이 헷갈릴 때는 for문을 사용하자. 
• while문을 통해 전체 문자열을 순회할 생각이었는데, pop할 때마다 인덱스를 조정해주지 않으면 IndexError가 발생할 수 있다. (예를 들어, 맨 마지막/앞이었을 때 등) 
• 또한 중간 위치의 원소를 pop(또는 remove)으로 제거하면, 제거된 원소 뒤에 위치한 모든 원소들을 전부 1칸씩 당겨와야 하므로 시간 복잡도가 O(N)이 된다.
• 그러므로, 위의 solution처럼, 따로 스택 변수를 두어 맨 앞의 원소를 pop / push 하는 것이 좋다. 

class Solution:
    def removeStars(self, s: str) -> str:

        d = list(s)
        i = 0

        while 0 <= i < len(d):
            if d[i] == '*':
                d.pop(i-1) # 일반 문자 제거
                d.pop(i-1) # * 제거
                i -= 1  # 두 문자열이 제거 되었으므로 다시 검사
            else:
                i += 1

        return ''.join(d)