[leetcode][1209] Remove All Adjacent Duplicates in String II

문제 : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

---

{문자, 문자가 연속으로 나온 횟수}를 요소로 하는 stack을 하나 만든다.

문자열 s를 앞에서부터 탐색하면서 스택이 비어있거나 스택 top에 있는 요소의 문자가 탐색중인 문자와 같다면 top 요소의 문자가 연속으로 나온 횟수를 +1 해준다.

그리고 만약 스택 top의 연속 횟수가 k와 같다면 stack을 pop 시킨다.

모든 문자열 s를 탐색하면서 stack을 세팅했다면

stack을 pop하면서 정답 문자열 앞에 문자열을 추가하면서 정답을 구할 수 있다.

시간 복잡도는 O(N). (N = |s|)

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1209.%20Remove%20All%20Adjacent%20Duplicates%20in%20String%20II.cpp