[leetcode][921] Minimum Add to Make Parentheses Valid

문제 : https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

---

스택을 이용한다.

스택에는 열린 괄호가 나올 때 이를 저장한다.

문자열 S를 처음부터 모두 탐색하면서

만약 문자가 열린 괄호라면 스택에 push한다. 

문자가 닫힌 괄호이고 스택이 비어있지 않은 경우 스택을 pop해준다.

ex) () -> 파란색 여는 괄호가 빨간색 닫는괄호의 짝이 된다.

문자가 닫힌 괄호이고 스택에 아무것도 없는 경우 열린 괄호가 하나 더 필요하다는 의미이므로 정답 + 1을 해준다.

ex) ()) -> 짝이 없는 닫힌 괄호

문자열 S를 모두 탐색했을 때 스택의 크기(짝이 없는 여는 괄호)를 정답에 더해준다.

ex) ())((

시간복잡도는 O(|S|).

---

소스코드 : https://gist.github.com/fpdjsns/bb1fc36f1ad4c2d9f19f100051da1bef