올바른 괄호

코딩테스트 문제

프로그래머스

 

문제 접근)
'('문자로 열려있으면 짝지어서 ')' 문자로 닫혀야 하므로 스택의 ( )의 인접한 한쌍이 있으면 제거하면 됩니다.
문자열의 길이 10^5이므로 시간 복잡도 O(N^2)미만의 알고리즘으로 해결하면 됩니다.

 

정답 및 해설

function solution(s) {
    let stack = [];
    if (s[0] === ")") return false; // ')' 닫는게 먼저 시작되면 '('')' 짝지어서 스택에서 없앨수 없으므로 false
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") { // '(' 여는게 오면 스택의 저장
            stack.push('(');
        } else { // ')' 닫힌게 오면 스택에서 '(' 하나 꺼내서 제거
            stack.pop();
        }
    }
    
    // stack의 길이가 0이면 짝지어서 모두 제거 됐으므로 true 아니면 false
    return stack.length === 0 ? true : false;
}