문제 개요
균형 잡힌(balanced) 괄호 문자열 S가 주어졌을 때, 아래 규칙에 따라 해당 문자열의 점수를 계산하는 문제입니다.
- () 의 점수는 1입니다.
- AB 의 점수는 A + B 입니다. (A와 B는 각각 균형 잡힌 괄호 문자열)
- (A) 의 점수는 2 × A 입니다. (A는 균형 잡힌 괄호 문자열)
예를 들어 입력 문자열이 "(()(()))" 라면, 내부 구조가 () 와 (()) 로 나뉘고 최종 점수는 6이 됩니다.
접근 방법: 스택 활용
이 문제는 스택(stack) 자료구조를 사용하면 깔끔하게 해결할 수 있습니다. 여는 괄호를 만나면 마커(-1)를 스택에 쌓고, 닫는 괄호를 만나면 스택 위의 값들을 하나의 점수로 병합하는 방식입니다. 전체 알고리즘은 다음과 같습니다.
- ans := 0 으로 초기화하고, 정수형 스택 st 를 선언합니다.
- i 를 0부터 문자열 S의 길이까지 반복합니다.
- S[i] 가 여는 괄호 '(' 라면, 스택에 -1 을 삽입합니다.
- 그렇지 않다면(닫는 괄호 ')' 인 경우):
- 스택의 top 이 -1 이면, 이는 빈 괄호 "()" 이므로 pop 한 후 1 을 삽입합니다.
- 그렇지 않으면:
- x := 0 으로 초기화합니다.
- top 이 -1 이 아닌 동안 x 에 top 값을 더하고 pop 을 반복합니다.
- x := x * 2 로 갱신합니다.
- -1 마커를 pop 하고, x 를 스택에 삽입합니다.
- 스택이 빌 때까지 모든 값을 ans 에 더하며 pop 합니다.
- ans 를 반환합니다.
여기서 -1 은 "여는 괄호"를 나타내는 특수 마커 역할을 하며, 닫는 괄호를 만날 때마다 해당 괄호 쌍이 감싸는 내부 점수들을 집계하고 2배로 곱해 다시 스택에 넣는 것이 핵심 아이디어입니다.
예제 코드
아래는 위 알고리즘을 C++ 로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int scoreOfParentheses(string S) {
int ans = 0;
stack <int> st;
for(int i = 0; i < S.size(); i+=1){
if(S[i] == '('){
st.push(-1);
}else{
if(st.top() == -1){
st.pop();
st.push(1);
}else{
int x = 0;
while(st.top() != -1){
x += st.top();
st.pop();
}
x *= 2;
st.pop();
st.push(x);
}
}
}
while(!st.empty()){
ans += st.top();
st.pop();
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.scoreOfParentheses("(()(()))"));
}입력
"(()(()))"
출력
6
동작 과정 살펴보기
입력 "(()(()))" 는 가장 바깥쪽 괄호 안에 "()" 와 "(())" 두 부분이 포함된 구조입니다. "()" 의 점수는 1, "(())" 의 점수는 2 × 1 = 2 이므로 내부 합계는 3이 되고, 최종적으로 2 × 3 = 6 이 반환됩니다. 이처럼 스택 기반 접근은 중첩된 괄호 구조를 자연스럽게 처리할 수 있으며, 시간 복잡도는 O(N), 공간 복잡도는 O(N) 입니다.