[리트코드] 1614 - Maximum Nesting Depth of the Parentheses

1614. Maximum Nesting Depth of the Parentheses

Easy

---

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

• 1 <= s.length <= 100
• s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
• It is guaranteed that parentheses expression s is a VPS.

분류

문자열, 스택, Bracket Sequences

---

문제 풀이

문제 분석

이 문제는 **유효한 괄호 문자열(VPS, Valid Parentheses String)**이 주어졌을 때, 괄호의 **최대 중첩 깊이(nesting depth)**를 구하는 것입니다.

• 입력: 숫자(0-9), 연산자(+, -, *, /), 괄호 '(', ')'로 구성된 문자열 s (길이 1 ~ 100). 입력은 항상 올바른 괄호 문자열임이 보장됩니다.
• 출력: 문자열 내에서 괄호가 가장 깊게 중첩된 정도를 나타내는 정수.
• 예시: "(1+(2*3)+((8)/4))+1"에서 숫자 8은 (( ... )) 안에 있으므로 깊이는 3입니다.

---

접근 방법

이 문제는 **단순 순회(Iteration)**와 카운터(Counter) 변수 두 개만으로 해결할 수 있습니다. 스택(Stack) 자료구조를 사용할 수도 있지만, 괄호의 종류가 '(' 하나뿐이고 유효성이 보장되므로 스택에 문자를 저장할 필요 없이 현재 깊이를 나타내는 정수 변수만 관리하면 됩니다.

핵심 아이디어:

1. 문자열을 왼쪽부터 오른쪽으로 한 글자씩 읽습니다.
2. 여는 괄호 '('를 만나면 현재 깊이를 1 증가시키고, 최대 깊이를 갱신합니다.
3. 닫는 괄호 ')'를 만나면 현재 깊이를 1 감소시킵니다.
4. 그 외 문자는 무시합니다.
5. 순회가 끝나면 기록된 최대 깊이를 반환합니다.

이 방식은 O(N) 시간에 O(1) 공간으로 최적의 성능을 보장합니다.

---

구현 설명

1. 변수 초기화

answer = 0
tmp = 0

• answer: 전체 문자열을 통틀어 발견한 최대 깊이를 저장하는 변수입니다. 초기값은 0입니다.
• tmp: 현재 순회 지점에서의 **현재 깊이(current depth)**를 나타내는 변수입니다. 초기값은 0입니다.

2. 문자열 순회 및 깊이 계산

for x in s:
    if x == "(":
        tmp += 1
        answer = max(tmp, answer)
    elif x == ")":
        tmp -= 1

• 문자열 s의 각 문자 x를 순회합니다.
• 여는 괄호 '('인 경우:
  • tmp를 1 증가시켜 한 단계 더 들어갔음을 표시합니다.
  • answer와 현재 tmp를 비교하여 더 큰 값으로 answer를 갱신합니다. 이것이 최대 깊이를 추적하는 핵심 로직입니다.
• 닫는 괄호 ')'인 경우:
  • tmp를 1 감소시켜 한 단계 빠져나왔음을 표시합니다. 유효한 괄호 문자열이므로 tmp가 음수가 될 일은 없습니다.
• 그 외 문자(숫자, 연산자):
  • 별도의 처리 없이 그냥 넘어갑니다. 깊이에 영향을 주지 않기 때문입니다.

3. 결과 반환

return answer

• 모든 문자 순회가 끝난 후, 최종적으로 기록된 최대 깊이 answer를 반환합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N)
  • N은 입력 문자열 s의 길이입니다. 문자열을 처음부터 끝까지 정확히 한 번만 순회하므로 연산 횟수는 N에 비례합니다.
• 공간 복잡도: O(1)
  • 입력 크기와 무관하게 정수 변수 두 개(answer, tmp)만 사용하므로 상수 공간만 필요합니다. 스택을 사용하지 않아 공간 효율이 매우 좋습니다.

---

핵심 포인트

1. 스택 불필요: 괄호의 유효성이 보장되고 종류가 하나뿐이므로, 스택에 괄호를 쌓는 대신 현재 깊이를 나타내는 정수 카운터 하나로 상태 관리가 가능합니다.
2. 최대값 갱신 시점: 여는 괄호 '('를 만나 깊이가 늘어난 즉시 최대 깊이(answer)를 갱신해야 합니다. 닫는 괄호에서 갱신하면 안 됩니다.
3. 문자 필터링: 괄호가 아닌 문자(숫자, 연산자)는 깊이에 아무 영향을 주지 않으므로 if-elif 구조로 괄호만 선별하여 처리하고 나머지는 무시하는 것이 깔끔합니다.

풀이 코드

class Solution:
    def maxDepth(self, s: str) -> int:
        answer = 0
        tmp = 0
        for x in s:
            if x == "(":
                tmp += 1
                answer = max(tmp, answer)

            elif x == ")":
                tmp -= 1           

        return answer