본문 바로가기
알고리즘 문제/Leetcode

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

by 햄과함께 2018. 10. 28.
320x100

문제 : 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



320x100

댓글