문제

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

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

해결

function solution(s){
    const sArr = s.split('');
    const stack = [];
    sArr.forEach((currentS) => {
        const prevS = stack[stack.length - 1];
        if(prevS === '(' && currentS === ')') {
            stack.pop();
        } else {
            stack.push(currentS);    
        }
    });
    return stack.length === 0;
}

과정

이전에 햄버거 만드는 문제와 비슷한 과정으로 문제를 해결할 수 있다.

시간복잡도

1. String.split(...) : s 의 길이에 영향을 받는 O(n) 의 시간복잡도를 가진다.
2. Array.forEach(...) : sArr 의 길이만큼 루프를 돌기 때문에 O(n) 의 시간복잡도를 가진다.
3. stack.push, stack.pop : 스택에 푸쉬하고 팝하는 과정은 O(1) 의 시간복잡도를 가진다.

전반적인 시간복잡도를 고려해보면 forEach 문 안에서의 로직은 시간복잡도에 영향을 주지 않고 있기 때문에 forEach 관련 로직은 O(n), split 관련 로직도 O(n) 이기에 총 O(n) 의 시간복잡도를 가지는 로직이 된다.