[프로그래머스] 올바른 괄호 (Lv 2) - javascript

문제

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

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
   

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

 

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

풀이

1차 풀이

function solution(s){

    let stack = [];

    for(let i = 0; i < s.length; i++) {

        if(s[0] === ')') { // 맨 처음이 ) => false
            return false;
        }

        if(s[i] === '(') stack.push(1); // stack에 값 추가
        else {
            if(stack.length === 0) return false; // 만약 pop할 값이 없음 => false
            else stack.pop(); 
        }
    }
    return stack.length ? false : true; // stack이 비어있다면 true
}

 
스택을 사용해서 풀었다.
(만큼 값을 채우고 )이 나오면 삭제하는 과정을 구현했다.
그렇게 해서 마지막에 스택이 비어있으면 true를 반환하게 했다.
구현하는 과정이 어렵지 않았으나 예외 처리가 여러 개 있어서 수정을 여러 번 했다.
아래 다른 분들의 풀이를 보니 이렇게 예외처리가 많지 않았고 더 간결했다.
 
또한 정확도는 통과했으나 효율성의 두번째 테스트를 통과하지 못했다.
단계가 줄어들도록 살짝 수정했더니 통과할 수 있었다.
 

2차 풀이

function solution(s){

    let stack = [];

    if(s[0] === ')') { // 반복문마다 검사하지 않도록 위로 빼줌
        return false;
    }

    for(let i = 0; i < s.length; i++) {

        if(s[i] === '(') stack.push(1);
        else {
            if (!stack.pop()) return false; // 과정을 간결히 수정
        }
    }
    return stack.length ? false : true;    
}

 

• 정확도 테스트 결과

  

  
   

• 효율성 테스트 결과
  

  

  
   

📌모범 풀이

function solution(s){

    let sum = 0;

    for(let i = 0; i < s.length; i++) {

        sum += s[i] === '(' ? 1 : -1;

        if(sum < 0) return false;
    }

    return sum ? false : true;
}

 
굳이 스택을 사용하지 않고, 변수로 숫자를 더하고 빼줬다.
속도도 훨씬 단축됐다.
생각하고 나면 참 간단한 풀이.

 

• 정확도 테스트 결과
  

  

  
   
• 효율성 테스트 결과