[leetCode] Valid Parentheses

20 . 유효한 괄호

 

 

'(', ')', '{', '}', '[', ']' 문자만 포함된 문자열이 주어지면 입력 문자열이 올바른지 확인합니다.

입력 문자열은 다음과 같은 경우에 유효합니다:

열린 브래킷은 동일한 유형의 브래킷으로 닫아야 합니다.
열린 브래킷은 올바른 순서로 닫아야 합니다.
모든 근접 브래킷에는 동일한 유형의 해당 개방 브래킷이 있습니다.

 

예 1:

입력: s = "()"
 출력: 참

예 2:

입력: s = "()[]{}"
 출력: 참

예 3:

입력: s = "(]"
 출력: 거짓

 

문제정리
주어진 괄호 문자열 's' 가 유효한 괄호인지를 검사하는 문제이다.
*처음에 오는 괄호 문자열은 무조건 ({[ 열린 괄호여야한다.
*유효한 괄호가 아니더라도 열린 괄호 닫힌 괄호 형태로 s 문자열이 주어진다. ex: (}, [}

생각한 풀이방법
1. 빈 배열을 만들어서 그안에 문자열 's'를 넣어주고 하나씩 가져와서 괄호 쌍이 맞으면 true를 반환하고 스택은 하나씩 비워진다.
2. 문자열 's'를 비교해주기위해 비교 잣대를 하나 만들어준다.
3. 비교잣대와 문자열 's'를 비교해서 열린괄호가 나타나면 배열에 넣어준다.
4. 열린 괄호가 아닐경우엔 pop() 메서드를 사용하여 배열의 마지막 요소를 제거하고 제거된 요소를 반환해서 변수에 저장시킨다.
5. 저장된 변수를 조건문을 통해 맞는 유효한 괄호를 찾아준다.
6. 최종 배열에 길이가 0이면 유효한 괄호가 남아있지않는 경우이기때문 true 아니면 false를 반환한다.

 

작성코드📌

function isValid(s) {
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    const char = s.charAt(i);
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      const top = stack.pop();
      if ((char === ')' && top !== '(') ||
          (char === ']' && top !== '[') ||
          (char === '}' && top !== '{')) {
        return false;
      }
    }
  }
  return stack.length === 0 ? true : false;
}

 

우선 문제는 주어진 괄호 문자열 's' 가 유효한 괄호인지를 검사하는 문제이다.

빈 스택을 만들어서 그안에 문자열 's'를 넣어주고 하나씩 가져와서 괄호 쌍이 맞으면 true를 반환하고 스택은 하나씩 

비워진다.

 

접근방법✏️

1. [] 배열의 다양한 메서드를 사용하기위해 빈 스택 배열을 세팅해준다.

 

2. charAt()메서드를 사용하여 s배열의 i번째 요소들을 넣어서 비교대상을 지정해준다.

 

2. 유효한 괄호를 만들려면 맨 처음에 오는 괄호는 반드시 열린 괄호 '(' 이기때문에 열린괄호 일 땐, 

push() 메서드를 사용하여 빈 stack에 넣어주었다.

 

3.위에서 push로 저장된 stack에  pop()메서드로 배열의 마지막 요소를 제거시키고 제거된 요소를 top 변수에 할당한.

- else 블록에서는 닫는 괄호인 경우 스택에서 마지막으로 삽입된 여는 괄호를 제거하여(정확하게는 top변수에 할당됨)

해당하는 닫는 괄호와 짝이 맞는지 검사한다.

 

4. 검사 결과, 짝이 맞지 않는 경우에는 false를 반환

 

5. 검사를 마친 후에도 스택이 비어있지 않은 경우에는 괄호 쌍이 맞지 않는 경우이므로 false를 반환한다.

그렇지 않은 경우에는 모든 괄호 쌍이 맞아서 유효한 괄호 문자열이므로 true를 반환한다.