코드카타 08: isValid

김현수·2022년 4월 20일
0

s는 여러 괄호들로 이루어진 String 인자입니다. s가 유효한 표현인지 아닌지 true/false로 반환해주세요.
종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다.
아래의 경우 유효합니다.

  • 한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
  • 괄호 순서가 맞아야 한다.

예를 들어 아래와 같습니다.

s = "()"   // return true
s = "()[]{}"  // return true
s = "(]"  // return false
s = "([)]"  // return false
s = "{[]}"  // return true

내가 푼 답

function isValid(s) {
  // 여기에 코드를 입력해주세요.

  if (s.length % 2) {
    return false;
  }
  
  const stack = [];

  const bracketMatching = {
    "(": ")",
    "{": "}",
    "[": "]",
  };

  for (let i = 0; i < s.length; i++) {
    if (bracketMatching[s[i]]) {
      stack.push(s[i]);
    } else if (bracketMatching[stack.pop()] !== s[i]) {
      return false;
    }
  }

  return true;
}

문제를 보자마자 누구나 자료 구조와 알고리즘 책에서 본 문제임을 알았고, 스택 구조로 풀어야겠다고 생각했다. stack이라는 빈 배열을 생성해두고, pushpop 메서드만을 사용해 문제를 풀어나갔다.

처음에는 if (s.length % 2) return false; 라는 조건을 달지 않았는데, 테스트 케이스 중 "("인 것이 있었고, 만일 글자 수가 홀수라면 당연히 짝이 맞지 않는 것이니 로직의 진행에 앞서 가장 먼저 심사 후 처리해주었다.

여는 괄호라면 stack 배열에 추가하고, 닫는 괄호라면 stack을 팝해 bracketMatching 객체에 넣어 짝이 맞는지 검사한다. 만일 맞는 짝이라면 추가 동작을 하진 않지만, stack에선 이미 마지막으로 들어간 여는 괄호가 pop되어 나간 상태라는 점을 이용했다.

0개의 댓글