꒰ྀི 06. 프로그래머스:: 올바른 괄호

 

문제 설명

 

열린 괄호가 닫힌 괄호로 닫히는지 확인해야 한다.

자료구조

 

바깥쪽부터 확인해주어야하기 때문에 후입선출 방식인 스택을 활용했다.

(를 스택에 추가하고, )가 나오면 열린 괄호를 제거한다.

해결 방법

 

1. s를 처음부터 끝까지 순회한다.

2. (가 나오면 스택에 추가한다.

3. )가 나오면 스택에서 열린 괄호를 제거한다.

4. 스택이 비었다면 모든 괄호가 짝지어졌으므로 true 반환, 아니라면 false 반환

 

function solution(s) {
    const stack = [];

    for (let char of s) {
        if (char === '(') {
            stack.push(char);
        } else {
            if (stack.length === 0) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.length === 0;
}

 

카운터를 활용한 코드도 확인할 수 있었다.

괄호의 짝을 맞추는 것은 단순히 카운터를 사용해 유지할 수 있다.

 

이 경우 메모리 사용이 적으며, 구현이 간단하다.

function solution(s){
    let cum = 0
    for (let paren of s) {
        cum += paren === '('? 1: -1
        if(cum < 0) {
            return false
        }
    }
    return cum === 0? true: false;
}

 

그래도 자료구조를 연습하는 주차이므로 스택을 활용해 풀이한 것을 선택하도록 하겠다.