[LeetCode] 856. Score of Parentheses

문제 : https://leetcode.com/problems/score-of-parentheses/

---

 

문자열 S를 앞에서부터 탐색한다.

스택을 사용하는데 여기에는 닫는 괄호가 나와서 유효한 값이 생기면 계산된 양수가 아직 닫는 괄호랑 짝지어지지 않은 여는 괄호는 0을 저장한다.

탐색 중 여는 괄호가 나오면 스택에 0을 push 한다.

닫는 괄호가 나오면 스택에 있는 수를 탐색하여 해당 닫는 괄호와 짝이 되는 여는 괄호 사이에 있는 괄호들의 두 번째 조건 AB = A + B 를 계산한다. ex) (()()) -> 진한 괄호들의 연산 1 + 1 계산

짝이 되는 여는 괄호는 스택에 존재하는 0 중 가장 위에 있는 값이다. 따라서 스택의 top이 0이 나오기 전까지 pop 되어 나오는 숫자들을 모두 더한다.

모두 더한 값이 0이라면 해당 괄호안에는 짝이 되는 괄호가 하나도 존재하지 않는 경우이므로 여는 괄호와 짝이 되는 닫는 괄호를 하나 찾은 것이 된다. 따라서 첫 번째 조건인 () = 1을 적용하여 스택에는 1을 넣어준다. ex) (). 더한 값이 0 이상이라면 세 번째 조건 (A) = 2* A 를 적용하여 곱하기 2한 값을 스택에 넣어준다. ex) (()) -> 1 * 2 = 2.

모든 문자열을 탐색한 뒤 스택에 있는 수를 다 더하면 정답이 된다. ex) (()) () (()) -> 2 + 1 + 2

 

시간 복잡도는 문자열 S를 한 번 탐색하고 닫는 괄호가 한 번 나올 때 큐를 탐색한다. 큐에 들어갈 수 있는 최대 크기는 여는 괄호의 크기이므로 |S|/2 이다. 따라서 시간 복잡도는 O(|S|2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/856.%20Score%20of%20Parentheses.cpp