Codility [ Lesson 7 | Stacks and Queues ] Nesting - JavsScript

Sohyeon Bak·2022년 3월 1일

Codility

목록 보기

16/19

문제

A string S consisting of N characters is called properly nested if:

S is empty;
S has the form "(U)" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

function solution(S);

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..1,000,000];
string S consists only of the characters "(" and/or ")".

문제해석

S에는 문자열로 소괄호가 주어진다. 괄호의 형태가 갯수와 순서에 맞게 중첩이 되어있으면 1을 리턴하고 그렇지 않다면 0을 리턴해야한다. (빈 문자열일 경우도 1을 리턴해야한다.)

문제 풀이

stack에 '('에 해당하면 push, ')'에 해당하면 pop을 해준다.
순서에 맞게 괄호가 주어진다면 모든 문자열을 다 탐색한 후에는 stack은 빈 배열이 되어야한다.
빈배열이 되면 1을 리턴하고 그렇지 않다면 0을 리턴해주면 된다.

코드

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let answer = 1;
    let stack = [];

    for(let i = 0; i<S.length; i++){
        if(S[i]==='(') stack.push(S[i])
        else {
            if(stack.length > 0) stack.pop()
            else return answer = 0
        }
    }

    
    return answer = stack.length > 0 ? 0 : 1
}