[스택] 올바른 괄호

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

괄호로 구성된 문자열이 입력으로 주어질 때, 이들이 올바른 괄호이면 "YES", 아니면 "NO"를 출력한다.

(())()(())의 경우 올바른 괄호이나 (()()의 경우에는 올바른 괄호가 아니다.

 

 

👉 입력

첫 번째 줄에 괄호로 구성된 문자열이 주어진다.

문자열의 최대 길이는 30이다.

 

 

👈 출력

"YES" 혹은 "NO"를 출력한다.

 

 

💡 사용된 개념

Stack(스택)

특수한 목적을 가지는 자료구조로 순서가 있는 entry들의 자료구조이다.

Stack은 LIFO(Last-In, First-Out)의 구조로 저장된 data를 꺼낼 때 가장 최근에 들어간 data부터 꺼내진다.

Stack에 넣는 작업을 push, 꺼내는 작업을 pop이라고 하며 stack에 저장된 데이터의 끝부분을 top이라고 한다.

즉, top은 제일 마지막에 push된 data를 뜻한다.

 

 

Stack Error는 두 가지의 경우가 있다.

• Stack Overflow : 이미 가득찬 Stack에 data를 추가적으로 삽입(push)하려는 경우 발생하는 Error
• Stack Underflow : 이미 비어있는 Stack에서 data를 추가적으로 빼내려는(pop) 경우 발생하는 Error

 

 

📝 풀이

 

function solution(s) {
    let answer = "YES";
    let stack = [];

    for (const i of s) {
        if (i === "(") stack.push(i)
        else {
            if (stack.length === 0) return "NO";
            stack.pop();
        }
    }

    if (stack.length !== 0) answer = "NO"

    return answer;
}

let a = "(()(()))(()";
console.log(solution(a));

 

올바른 괄호인지 알아보기 위해 주어진 문자열을 순회한다.

 

여는 괄호 "(" 가 나왔을 때 stack에 해당 괄호를 넣는다.

닫는 괄호 ")"가 나왔다면 이 괄호는 stack에 넣지 않고 stack에서 빼내는 작업만 실행한다.

이 과정에서 이미 스택이 비어있었다면 이는 현재 괄호 ")"의 여는 괄호 짝이 없다는 뜻으로 올바른 괄호가 될 수 없으니 "NO"를 리턴한다.

 

모든 순회를 끝낸 후 stack이 비어있으면 괄호가 모두 제 짝이 있다는 뜻으로 올바른 괄호이나 아닐 경우 올바른 괄호가 아니므로 answer는 "NO"가 된다.