Intuition

stack 에 여는괄호 '(' 를 넣으면서 닫는괄호 ')' 가 나올 때마다 경우에 맞게 처리해주는 방식으로 풀이했다.

Approach

'(()())' 을 예시로 설명해보겠다. 그림으로 표현해보면 아래와 같은 상황이다. sp는 스택포인터다.
여는 괄호가 등장했으므로 스택에 여는 괄호를 의미하는 -1(임의숫자)을 push해준다. 이때 중요한 점은 '('를 그대로 넣지 않는다는 것이다. 여는 괄호도 결국에는 ascii table상 40이기 때문에 점수 계산을 양수인 숫자로 하는 우리에게 혼선을 준다.그 다음 경우도 마찬가지다.이번에는 닫는 괄호를 만났으므로 스택을 확인한다. 여는 괄호가 있기때문에 두 여닫는 괄호가 합쳐저 1점으로 바뀐다.이어서 계속 진행해준다.닫는 괄호를 만났으므로 -1이 나올 때까지 pop한다. 그리고 그 사이에 있는 점수들을 더한 후 2를 곱하여 push해준다.이제 모든 괄호를 다 확인했으므로 pop을 하면 자동으로 답이 튀어나온다.
그렇지만 아래 그림과 같이 합산해줘야 하는 경우도 있으므로 stack이 빌 때까지 pop하여 그 합을 결과값으로 반환한다.

Solution

int sp=0;
int arr[50];

void push(int ele){
    arr[sp++]=ele;
}

int pop(){
    return arr[--sp];
}

int scoreOfParentheses(char* s) {
    for (int i=0;s[i]!=0;i++){
        if(s[i]=='(') push(-1);
        else{
            int ele=pop();
            if(ele==-1) push(1);
            else{
                int tmp=0;
                while(ele!=-1){
                    tmp+=ele;
                    ele=pop();
                }
                push(2*tmp);
            }
        }
    }

    int res=0;
    while(sp>=1){
        res+=pop();
    }
    
    return res;
}

Time Complexity

$O(N)$

지적 및 질문 환영