2020.08.19 Valid Parentheses 풀이

문제 : Valid Parentheses

'(', ')', '{', '}', '[' ']' 만이 문자를 구성할 수 있다라고 할 때, 유효한 지 아닌지 판별하는 문제.

예를 들면 '{()}'은 유효하고, '{(}'은 유효하지 않은 문자열이다. 

 

풀이 : 

1) 주어진 문자열이 홀수면 반드시 유효하지 않다.

2) 문자열이 0이면, 반드시 유효하다.

3) 짝수의 문자열일 경우, 각각 여는 '(', '{', '['표현이 나오면 닫는 표현도 문자 반대 순서대로 나와야 한다.

여는 표현들이 나오면 arr 에 넣어주고, 닫힘 표현이 나오면 arr에 여는 표현이 있는지 체크 후, 있으면 제거 | 없으면 즉시 false

 

/**
 * @param {string} s
 * @return {boolean}
 */
 
var isValid = function(s) {
  let length = s.length, arr = [];
  
  if(length === 0) return true;
  if(legnth % 2 !== 0) return false;
  
  let par = {
    ')' : '(',
    '}' : '{',
    ']' : '['
  };
  
  for(let i = 0; i < length; i++) {
    let cur = s[i];
    let store = arr[arr.length -1];
    let match = par[cur]
    
    if(match) {
      if(store === match) {
        arr.pop(); // arr의 첫 원소 제거
      } else {
        return false;
      }
    }
  }
  
  return !arr.length
}

Runtime: 96 ms

Memory Usage: 36.7 MB

 

궁금해서 메모리를 더 적게 사용하고 더 빠른 런타임을 자랑하는 해답을 확인해 보았다.

 

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const openBrackets = '{([';
    const closingBrackets = '})]';
    const matchingBrackets = {
        '}':'{',
        ')':'(',
        ']':'['
    };
    const stack = [];
    for(const char of s){
        if(openBrackets.includes(char)){
            stack.push(char)
        }
        else if(closingBrackets.includes(char)){
            if(stack.length == 0){ //it becimes an uneven string
                return false;
            }
        
        if(stack[stack.length - 1] === matchingBrackets[char]){
            stack.pop();
        }
        else{
            return false;
        }
    }
}

 return stack.length === 0;
    
};

해당 방법 은 48 ms 의 방법이다. 전개는 비슷한데, 좀더 간소화한 느낌이라는 생각이 든다.

 

문득 궁금해져서 불필요한 변수 선언(let length = s.length)을 줄였더니 실행 속도가 82ms 로 훨씬 빨라졌으나, 메모리 사용량은 살짝 36.8로 살짝 높아졌다. 그리고 초반에 if문도 굳이 선언할 필요가 없어서 삭제했더니 역시나 속도가 빨라졌다. 무엇이 메모리의 사용량을 높이고 런타임속도에 영향을 주는 걸까 궁금해졌다. 알고리즘 10번 정도 연속적으로 풀고 나면, 어떤 요소들이 런타임 속도 / 메모리 사용량에 영향을 미치는지 좀 깊게 조사해볼 예정이다. 

 

https://leetcode.com/problems/valid-parentheses

Valid Parentheses - LeetCode