[LeetCode] 856. Score of Parentheses

문제링크

"("와 ")"로 이루어진 문자열이 주어졌을 때, 아래 규칙에 따라 해당 배열의 점수를 구하는 문제이다.

• "()"는 1점
• (A)에서 A가 균형 잡힌 괄호 문자열인 경우, A 점수의 2배
• AB의 점수는 A+B

이전에는 단순히 문자열이 균형 잡힌 배열인지 아닌지에 대한 문제들만 풀었어서, 어떻게 해결해야 할 지 상당히 고민이 많았다.

당연하게도 이 문제를 해결하기 위해서는 스택을 사용해야 하며, "("일 때는 스택에 push하고, ")"일 때는 스택에서 pop을 하는 규칙은 변함이 없다.

예를 들어 주어진 문자열이 "((()))(())"일 때, 점수는 6점이다.

1. ( ( ( ) ) ) ( ( ) ) -> 스택에 push

(

2. ( ( ) ) ) ( ( ) ) -> 스택에 push

(	(

3. ( ) ) ) ( ( ) ) -> 스택에 push

(	(	(

4. ) ) ) ( ( ) ) -> "("을 pop한 뒤 점수 계산. 이후 점수를 스택에 push

(	(	1

5. ) ) ( ( ) ) -> pop한 값이 숫자라면 그 숫자에 x2를 한후 스택에 다시 push를 반복한다. "("이 나오면 4번 과정을 진행한다.

(	2

6. ) ( ( ) ) -> 5번 과정과 마찬가지

4

7. ( ( ) ) -> 스택에 push

4	(

8. ( ) ) -> 스택에 push

4	(	(

9. ) ) -> 4번 과정 진행

4	(	1

10. ) -> 5번 과정 진행

4	2

11. stack이 empty가 될 때까지 pop하여 값들을 모두 더해준다. -> 4+2=6

이러한 과정을 코드로 정리하면 아래와 같다.
int 배열로 이루어진 stack을 생성하였고, "("는 -1로 표현하였다.

typedef struct stack_t {
    int items[100];
    size_t top;
} stack_t;

void s_init(stack_t* s) {
    s->top=0;
}

void s_push(stack_t* s, int item) {
    s->items[s->top++]=item;
}

char s_pop(stack_t* s, int* res) {
    *res = s->items[--s->top];
    return 0;
}

int s_is_empty(stack_t* s) {
    return s->top==0;
}

int scoreOfParentheses(char * s){
    stack_t stack;
    s_init(&stack);

    for(int i=0;i<strlen(s);i++)
    {
        if(s[i]=='(') s_push(&stack, -1);
        else
        {
            int count=0;
            int res;
            s_pop(&stack, &res);

            if(res==-1) {
                s_push(&stack, 1);
                continue;
            }

            while(res!=-1)
            {
                count=count+res*2;
                s_pop(&stack, &res);
            }
            s_push(&stack, count);

        }
    }

    int ans=0;

    while(!s_is_empty(&stack))
    {
        int answer;
        s_pop(&stack, &answer);
        ans+=answer;
    }

    return ans;
}