[Leetcode] 2390. Removing Stars From a String

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

---

문자열 s가 주어지며, s는 별표(*)를 포함합니다.

한 번의 작업에서 다음을 할 수 있습니다:

s에서 별표 하나를 선택합니다.

그 별표 왼쪽에서 가장 가까운 비 별표 문자를 제거하고, 그 별표 자체도 제거합니다.

모든 별표가 제거된 후의 문자열을 반환합니다.

 

참고

- 입력은 항상 작업이 가능하도록 생성됩니다.

- 결과 문자열은 항상 고유함이 보장됩니다.

---

stack을 사용합니다.

문자를 앞에서부터 탐색하면서 별표가 아닌 문자인 경우 스택에 문자를 넣습니다.

별표인 경우 스택의 탑에 있는 문자를 제거합니다.

모든 문자열을 탐색했으면 스택에서 문자를 제거하면서 정답 문자열의 뒤에서부터 채워나가면 정답을 구할 수 있습니다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/2390.%20Removing%20Stars%20From%20a%20String.cpp