[Codility] (Lesson7 | Stacks and Queues) Brackets - JavaScript

Sohyeon Bak·2022년 2월 26일

Codility

목록 보기

14/19

문제

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

S is empty;
S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

function solution(S);

that, given a string S consisting of N characters, returns 1 if 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..200,000];
string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

문제해석

stack 문제로 문자열이 주어지는데 모두 괄호가 주어진다. 문자열이 참인지 거짓인지 확인하는 문제로 참이 될 수 있는 경우는 3가지가 있다.
첫번째, 빈 문자열일 경우
두번째, "()", "[]", "{}"등과 같이 적절하게 중첩된 경우
세번째, "{()[]}"와 같이 여러개가 중첩됐으나 적절하게 중첩된 경우이다.

거짓을 반환하는 경우는 "[{}(]"와 같이 여는 소괄호에 맞는 닫는 소괄호가 없는 경우이다.
참일 경우 1을 거짓일 경우 0을 반환하면 된다.

문제풀이

문자열로 주어지는 데이터를 배열 형태로 만들어 준 다음 첫번째 문자열 부터 순서대로 탐색한다. 여는 괄호에 해당하면 stack으로 저장할 배열에 push를 해주고 닫는 경우는 push한 배열의 마지막이 일치하는 괄호인지 확인 한 후 pop을 해주면 된다. 적절하게 괄호가 주어졌다면 stack으로 담은 배열은 빈 배열이 될 것이다. 그렇지 않다면 적절하게 주어지지 않은 문자열이었음으로 0을 리턴하면 된다.

코드

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    if(S.length === 0) return 1

    let str = S.split('');
    let stack = [];
    for(let i = 0; i<str.length; i++){
        if(str[i]==='(' || str[i]==='[' || str[i]==='{') stack.push(str[i])
        else {
            if(stack.length===0) return 0    
            if(str[i]===')' && stack[stack.length-1]==='(') stack.pop()
            if(str[i]===']' && stack[stack.length-1]==='[') stack.pop()
            if(str[i]==='}' && stack[stack.length-1]==='{') stack.pop()
        }
    }
    return stack.length > 0 ? 0 : 1
}