leetcode856. Score of Parentheses
by EunHye Jung
856. Socre of Parentheses
괄호 문자열 S가 주어지면, 다음의 규칙으로 문자열의 점수를 계산.
()는 1점.- AB는
A+B를 점수로 가지고, A와 B는 올바른 괄호쌍 문자열. (A)는2 * A를 점수를 가짐. A는 올바른 괄호쌍 문자열.
Example 1
Input: “()”
Output: 1
Example 2
Input: “(())”
Output: 2
Example 3
Input: “()()”
Output: 2
Example 4
Input: “(()(()))”
Output: 6
Leetcode Artcle
접근법 1. Stack
점수를 계산하기 위해선, 괄호의 깊이(dpeth)를 이용한다. 깊이란 현재의 괄호 바깥으로 얼마나 많은 (아직 닫히지 않은) 열린괄호(로 둘려쌓여있는지를 뜻함.
예를 들어, (()(.()))에서 점(.)은 깊이 2를 가진다. -> (_ _ ( . _ _))
우리가 열린 괄호(를 만날때, 깊이를 증가시키고, 새로운 깊이에서 점수(score)는 0이다.(스택에 0을 push)
우리가 닫힌 괄호)를 만날때, 깊이를 줄여준다.
깊이를 줄여줄때 고려해야하는 사항은 ()인 경우에는 점수 1을 가지고, (A)는 2 * A의 점수를 가진다는 것이다.
따라서 현재 줄일 깊이의 괄호가 1의 점수를 가지는지, 2 * A의 점수를 가지는지는
Math.max(2 * stack.pop(), 1))을 통해 확인한다.
예를 들어, (()(()))의 점수를 매긴다고 할때 우리의 스택은 다음과 같은 값을 가질 것이다.
- string[0] :
(-> 깊이를 하나 더 증가시켜준다(push 0) : [ 0, 0] - string[1] :
(-> 깊이를 하나 더 증가시켜준다(push 0) : [0, 0, 0] - string[2] :
)-> 닫힌 괄호를 만났으니 깊이를 하나 줄여준다. : [ 0, 1] - string[3] :
(-> 깊이를 하나 더 증가시켜준다(push 0) : [0, 1, 0] - string[4] :
(-> 깊이를 하나 더 증가시켜준다(push 0) : [0, 1, 0, 0] - string[5] :
)-> 닫힌 괄호를 만났으니 깊이를 하나 줄여준다. : [ 0, 1, 1] - string[6] :
)-> 닫힌 괄호를 만났으니 깊이를 하나 줄여준다. : [ 0, 3] - string[7] :
)-> 닫힌 괄호를 만났으니 깊이를 하나 줄여준다. : [ 6 ]
public int scoreOfParentheses(String str) {
Stack<Integer> stack = new Stack();
stack.push(0);
for(char c : str.toCharArray()) {
if (c == '(')) {
stack.push(c);
} else {
int v = stack.pop()
int w = stack.pop();
stack.push(w + Math.max(2 * v, 1));
}
}
return stack.pop();
}
복잡도 분석
- 시간 복잡도 : O(N), N는 문자열 s의 길이
- 공간 복잡도 : O(N), 스택의 크기
Subscribe via RSS