[Codility - Counting Elements] Brackets

문제 링크

NumberOfDiscIntersections coding task - Learn to Code - Codility

 

- 스택 문제중에서도 가장 쉬운 문제인 것 같다. 백준 브론즈 냄새가..

 

- 자바스크립트는 C++처럼 stack STL을 제공하지 않지만, array를 잘 활용하면 stack과 queue를 사용할 수 있다.

 

- N은 200,000 이하의 양의 정수이다. 따라서, O(NlogN) 이하의 알고리즘을 구현해야 하고, 0일때 예외 처리를 해 주어야 한다.

 

function solution(S) {
    if(S.length === 0) return 1;

    let arr = [];

    for(let char of S) {
        if(char === '{' || char === '[' || char ==='(') {
            arr.push(char);
        } else {
            if(arr.length === 0) return 0; //여는 괄호 없이 바로 닫는 괄호가 나온 경우

            if(char === '}' && arr.pop() !== '{') return 0;
            if(char === ']' && arr.pop() !== '[') return 0;
            if(char === ')' && arr.pop() !== '(') return 0;
        }
    }

    if(arr.length !== 0) return 0

    return 1;
}

 

- 예외처리를 몇 가지 해 주어야 한다. 첫 번째는 N이 0인 경우 바로 0을 return 해 주고, 두 번째는 처음부터 닫는 괄호인 경우에는 바로 0을 return한다. 마지막은 S를 모두 순환하였을 때 arr에 값이 남아있는 경우 0을 return해야 한다.