[LeetCode] 1614. Maximum Nesting Depth of the Parentheses

https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/description/

Leetcode - Maximum Nesting Depth of the Paretheses

문제 유형 : 문자열 처리, 스택

문제 난이도 : Easy

 

문제

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

• It is an empty string "", or a single character not equal to "(" or ")",
• It can be written as AB (A concatenated with B), where A and B are VPS's, or
• It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

• depth("") = 0
• depth(C) = 0, where C is a string with a single character not equal to "(" or ")".
• depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's.
• depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a VPS represented as string s, return the nesting depth of s.

 

문자열이 아래의 조건중 하나라도 만족하면 VPS라 불린다:

• 빈 문자열, 또는 "("나 ")"가 아닌 하나의 문자
• 한 문자 A로 쓰일 수 있다.
• AB로도 쓰일 수 있다.(두 VPS의 접합이 가능하다)

 

VPS S를 아래의 조건으로 nesting depth를 구해야 한다.

• depth("") = 0
• depth(C) = 0 (C는 길이가 1인 문자열이나, 소괄호가 아니다.)
• depth(A + B) = max(depth(A) + depth(B)) (두 VPS A와 B)
• depth( "(" + A + ")" ) = 1 + depth(A)

풀이

설명이 장황한데, 읽어보면 결국 문자열의 소괄호의 최대 중첩을 구하는 문제이다.

문자열을 순차적으로 순회하면서, 여는 소괄호면 +1, 닫는 소괄호면 -1을 하면서, 최대 값을 갱신시키면 된다.

 

코드

C++

class Solution {
public:
    int maxDepth(string s) {
        int maxDepth = 0;
        int depth = 0;

        for(const auto &ch : s) {
            if(ch == '(') depth++;
            else if(ch == ')') depth--;
            maxDepth = max(maxDepth, depth);
        }

        return maxDepth;
    }
};