[2024] day 96. Leetcode 1614. Maximum Nesting Depth of the Parentheses

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 4일 (목)
Leetcode daily problem

1614. Maximum Nesting Depth of the Parentheses

https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/?envType=daily-question&envId=2024-04-04

Problem

주어진 문자열의 중첩된 괄호의 최대 깊이를 구하는 문제이다.

문제를 번역해보면,
문자열은 다음 중 하나를 충족하는 경우 유효한 괄호 문자열인 VPS로 표시한다.

문자열 s로 표현된 VPS가 주어지면 s의 중첩 깊이를 반환하는 것이다.

Solution

linear search (선형 탐색)

문자열을 한 번 순회하면서 각 문자를 확인하고, 열린 괄호를 만나면 깊이를 증가시키고, 닫힌 괄호를 만나면 깊이를 감소시킨다. 중첩 길이의 최댓값을 업데이트하면서 최대 중첩 길이를 찾는다.

Code

class Solution:
    def maxDepth(self, s: str) -> int:
        maxDepth = 0
        curDepth = 0
        
        for char in s:
            if char == '(':
                curDepth +=1
                maxDepth = max(maxDepth, curDepth)
                
            elif char ==')':
                curDepth -=1
                
        return maxDepth
        

Complexicity

시간 복잡도

주어진 문자열을 한번 순회하므로 시간복잡도는 O(1)이다.

공간 복잡도

추가적인 데이터 구조를 사용하지않고 상수 변수만 사용하므로 공간복잡도는 O(1)이다.