[Algorithm/JavaScript] Maximum Nesting Depth of the Parentheses

LeetCode Weekly Contest Question#1 Review 🤓

---

문제출처: https://leetcode.com/contest/weekly-contest-210/problems/maximum-nesting-depth-of-the-parentheses/

문제

문제설명

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(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.

예시

제한사항

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

---

제출답안

❌ Wrong Answer ❌

//s의 깊이를 반환하는 문제.
//즉, s안에서 ()가 몇 쌍이 들어있는지 판단해야함. 
//(가 나오면  +, )가 나오면 -를 해서 카운트할 것.
//)가 (에 연달아서 나오면 숫자가 감소해야하고, (에 똑같은 (가 연달아서 나오면 숫자가 증가해야한다.


var maxDepth = function(s) {
    let countOpenPer = 0;     // -1해야함.
    let countAll = 0;     //0으로 돌아오는 경우에만 countOpenPer반환할 것.
    let arrDepth = [];
    
        for (var i = 0; i < s.length; i++) {
            console.log("s[i]", s[i]);
            if (s[i] === "("){
                countOpenPer++;
                arrDepth.push(countOpenPer);
                countAll++; 
            } 
                    
            
            if (s[i] === ")"){
                countAll--;
                if (countAll === 0){
                    //'(' 카운트 초기화 
                    countOpenPer = 0;
                }         
            }
            
//               if (countOpenPer > maximumCount){
//                 maximumCount = countOpenPer; 
//                 console.log("maximumCount:", maximumCount);
//             }
            
        }
    
    if (countAll === 0){
        console.log("Math.max.apply(null, arrDepth) ", Math.max.apply(null, arrDepth) );
        return Math.max.apply(null, arrDepth) === -Infinity ? 0 : (Math.max.apply(null, arrDepth)); 
    } 
    
    //나머지의 경우 (쌍이 맞지 않는 경우)
    return 0;
};

⬆️ 위 오답에서 방황하고 있는 사이, contest의 제한시간이 모두 지나버렸다... 😂
다 내려놓고 처음부터 다시 풀어보았더니 아래 코드로 Pass 됐다!

⭕️ Right Answer ⭕️

//s의 깊이를 반환하는 문제.
//즉, s안에서 ()가 몇 쌍이 들어있는지 판단해야함. 
//'('가 나오면  push, ')'가 나오면 pop를 해서 요소를 추가/제거.


var maxDepth = function(s) {
    let arrCount = [];    
    let maximumLength = 0;
    
    for(var i = 0; i < s.length; i++){
        if (s[i] === "("){
            arrCount.push(0); 
        } else if (s[i] === ")"){
            arrCount.pop();
        }
        
        if (maximumLength < arrCount.length){
            maximumLength = arrCount.length;
        }
    }
    
   return maximumLength;
};

---

오늘의 Lesson

• 스택(stack): 가장 나중에 들어간 자료가 가장 먼저 나오는 구조로, '후입선출' 또는 'LIFO(Last in First Out)'라고도 함.
  
  (Image Reference: https://m.blog.naver.com/PostView.nhn?blogId=alsrb968&logNo=221183597931&proxyReferer=https:%2F%2Fwww.google.com%2F)
• 이런 유형의 문제는 배열의 스택(stack)구조와 push & pop 메소드를 이용하는 것이 좋다. 스택배열 구조를 활용하지 않고 괄호의 갯수를 담는 변수를 만들어 카운트할 경우, 여러 가지 test case를 모두 충족하는 조건문을 추가로 작성해야하는 번거로움이 따라온다.
• 여러 오답을 시도해 보다가 빈 배열을 만들어 필요한 데이터를 저장해야겠다는 발상(let arrDepth = [];)까지는 해보았으나, push와 pop메소드를 사용해 스택을 구현할 수 있다는 생각에는 미치지 못했었다.push연산, pop연산을 이용하면 어렵지않게 스택을 코드화 할 수 있다.
• +PLUS: 큐(queue)는 '선입선출'(FIFO, First in first out) 구조. 차이알기!
  (Reference: https://devuna.tistory.com/22)