[프로그래머스] 올바른 괄호 (JS / Stack)

 

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

문제 풀이

먼저, 이 문제를 쉽게 풀기 위해서 스택을 알아야한다.

 

스택(Stack)이란?

스택은 자료구조형으로 데이터를 일시적으로 저장하고, 빼는 후입선출 (LIFO, Last-In-First-Out) 원칙을 따른다.

스택은 push()와 pop()으로 수행할 수 있는데 push는 스택에서 데이터를 추가하고 pop은 데이터를 제거한다.

function solution(s){
    let stack = [];
    
    for (let i = 0; i < s.length; i++) {
        if(s[i] === '(') { // '(' 여는 괄호면 stack에 넣기
            stack.push(s[i])
        } else if(s[i] === ')') { // 닫는 괄호라면 stack 마지막이 여는 괄호일 때만 빼기
            if(stack.length !== 0 && stack[stack.length - 1] === '(') {
                stack.pop()
            } else return false
        }
    }
    return stack.length === 0
}

 

for문을 돌리는데 '(' 여는 괄호라면 stack에 저장해 놓고 ')' 닫는 괄호라면 조건에 맞을 때만 pop()을 해준다.

stack이 비어있지 않거나, stack의 마지막 괄호가 여는 괄호일 때(한 쌍이어야하니까)만 pop()으로 빼준다.

stack이 다 비워졌다면 true를 그렇지 않다면 false를 반환한다.