[Codility] Lesson 7: Stacks and Queues - Brackets (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

Brackets coding task - Learn to Code - Codility

- N 개의 문자로 구성된 문자열 S가 주어짐
- 문자열 S는 "(", "{", "[", "]", "}" 또는 ")"의 문자로만 구성됨
- 괄호 식이 올바르면 1을, 아니면 0을 return
- N은 [0..200,000] 범위 내의 정수
- 가장 효율적인 알고리즘 작성

 

 

Solution

CASE 1: 배열을 이용해 스택 형식으로 해결 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = S.length;
    let stack = [];
    
    for(let i=0; i<N; i++){
        switch(S.charAt(i)){
            case '(':
            case '{':
            case '[':
                stack.push(S.charAt(i));
                break;
            case ')':
                if(stack[stack.length-1] == '('){
                    stack.pop();
                }
                else{
                    return 0;
                }
                break;
            case '}':
                if(stack[stack.length-1] == '{'){
                    stack.pop();
                }
                else{
                    return 0;
                }
                break;
            case ']':
                if(stack[stack.length-1] == '['){
                    stack.pop();
                }
                else{
                    return 0;
                }
                break;
        }
    }
    
    if(stack.length > 0){
        return 0;
    }
    else{
        return 1;
    }
}

- N : 문자열 S의 길이
- stack : 문자열 S의 왼쪽 괄호들을 저장할 배열(스택)
- 왼쪽 괄호이면 stack에 push
- 오른쪽 괄호이면 스택의 top을 비교
    해당 괄호에 맞는 왼쪽 괄호가 있으면 pop
    해당 괄호에 맞는 왼쪽 괄호가 없으면 0을 return
- for문이 종료되면 stack의 length를 확인해 결과 return
    length > 0 : stack에 짝이 맞지 않는 왼쪽 괄호가 남아있다는 소리이므로 0을 return
    length = 0 : stack이 비어있는, 모든 괄호가 짝이 맞는다는 소리이므로 1을 return

 

CASE 1: Result

app.codility.com/demo/results/trainingGBXCTA-SN4/

 

CASE 1: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

가장 마지막에 열린 괄호부터 순서대로 닫혀야되기 때문에 후입선출 구조인 스택을 이용
=> Array의 push, pop 기능 이용

대신, Array에는 스택의 top 함수가 없기 때문에 [배열의 길이 -1]로 top 값을 확인

switch case문을 사용하니까 왼쪽 괄호('(', '{', '[')의 경우에는 편리한데 오른쪽 괄호(')', '}', ']')인 경우 비슷한 소스 코드가 중복되는 것 같아서 수정을 해보려고 했는데 뭔가 점점 더 복잡해지는 느낌이라 그냥 여기서 마무리.
조금 더 깔끔하게 할 수 있는 방법을 생각해봐야 할 듯.