[알고리즘 - LeetCode] Valid Parentheses

김혜진·2019년 11월 26일

algorithms

목록 보기

4/8

문제

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

(), {}, [] 괄호로 이루어진 문자열이 주어졌을 때 해당 문자열이 유효한지 확인하라.
유효성은 아래의 기준으로 판단한다.

1. 열린 괄호와 닫힌 괄호가 같은 타입이어야 한다.
2. 열린 괄호의 순서대로 닫힐 괄호가 있어야 한다.
3. 빈 문자열도 유효한 것으로 취급한다.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

풀이

제출 코드

const isValid = function(s) {
    if (s.length % 2 !== 0) return false;
    
    const pairs = {
        '{': '}',
        '[': ']',
        '(': ')'
    };
    
    let stack = [];
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '{' || s[i] === '[' || s[i] === '(') {
            stack.push(s[i]);
            continue;
        }
        
        if (pairs[stack[stack.length - 1]] === s[i]) {
            stack.pop();
            continue;
        }
        return false;
    }
    return stack.length === 0;
};

이전에 부트캠프 프렙 과제로 같은 유형의 문제를 풀었던 기억이 있다.
그땐 셀 수 없는 조건문의 향연으로 풀었던 것 같은데... 아, 그리고 문자열을 굳이 split해서 배열로 만들었던 것 같기도 하다.
아무튼 '아는 만큼 보인다'고 자료 구조를 알고 나니 stack최적화 알고리즘 같다.
1. 주어진 문자열을 순회하며
2. 열린 괄호를 stack 배열에 넣고
3. 닫힌 괄호가 나올 시 상수로 선언한 pairs 객체에서 stack의 마지막 열린 괄호를 key 값으로 찾았을 때 value값이 현재 순회 중인 닫힌 괄호와 일치하는지를 확인한다.

타 제출 코드와 실행 속도 비교

스크린샷 2019-11-25 오전 2.03.46.png

개선 사항

실행 속도가 가장 빠른 코드

const isValid = function(s) {
  if (s === "") return true;

  const openP = ['(', '[', '{']
  const closeP = [')', ']', '}']
  let curP;
  let pStack = [];

  for (let p of s) {
    if (closeP.includes(p)) {
      curP = pStack.pop();
      if (!curP || curP !== openP[closeP.indexOf(p)]) return false;
    } else {
      pStack.push(p);
    }
  }

  return pStack.length === 0;
};

for..of문으로 순회하고 괄호들을
배열로 나누어 배열 메소드들 includes, indexOf을 사용해서
stack구조로 해결했다.

코드 흐름은 크게 다르지 않은데 내 코드에서는 객체로 괄호들을 나누어 둔 것을 배열로 각각 만들어 둔 것이 가장 큰 차이점 인 듯 하다.
만약 다른 종류의 괄호가 있을 시 배열에 추가해서 메소드로 확인하면 되니 간편한 것 같아서 비슷한 맥락으로 객체도 키 값이 있는지 확인하는 hasOwnProperty 메소드를 사용해서 변경 해보았다.

변경 후 코드

const isValid = function(s) {
    if (s.length % 2 !== 0) return false;
    
    const pairs = {
        '{': '}',
        '[': ']',
        '(': ')'
    };
    
    let stack = [];
    
    for (let i = 0; i < s.length; i++) {
        if (pairs.hasOwnProperty(s[i])) { // hasOwnProperty사용으로 키 값 확인
            stack.push(s[i]);
            continue;
        }
        
        if (pairs[stack[stack.length - 1]] === s[i]) {
            stack.pop();
            continue;
        }
        return false;
    }
    return stack.length === 0;
};