본문 바로가기
Algorithm

[프로그래머스] 올바른 괄호 | JavaScript

by Vintz 2021. 7. 2.
반응형

올바른 괄호

문제 설명

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

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

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

제한사항

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

입출력 예

s answer
"()()" true
"(())()" true
")()(" false
"(()(" false

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

코드

첫번째 시도

function solution(s){
 let answer = true;
    
 if(s.charAt(0) === ')' || s.charAt(s.length-1) === '(') answer = false; 
    
 return answer;
}

단순하게 생각해서 첫 문자열과 마지막 문자열에 '(' 문자로 열리거나 ')' 문자로 닫히지 않았다면 false를 반환하게 했다. 첫 코드 실행은 무난히 통과 되었지만 여러 테스트 케이스에서 실패가 뜨게 되었다.

3개의 정확성 테스트 실패, 1개의 효율성 테스트 실패 (73.2 / 100.0)

두번째 시도

function solution(s){
 let answer = true;
    
 if(s.charAt(0) === ')' || s.charAt(s.length-1) === '(') answer = false; 

 const a = s.split('').filter((s) => s === '(').length;   
 const b = s.split('').filter((s) => s === ')').length; 
    
 if(a !== b) answer = false;
    
 return answer;
}

이번엔 "첫번째 조건문을 통과 했을 경우 '(' 문자와 ')' 문자의 개수가 다르면 false이지 않을까?"라는 생각으로 구현해봤다.

2개의 정확성 테스트 실패 (92.3 / 100)

이번엔 거의 근접했다. 하지만 정확성에서 떨어진다. 어떤 경우에서 내 알고리즘이 실패가 뜨는지 알기 위해 프로그래머스 질문하기 도움을 받기로 했고 그 경우는 다음과 같았다.

  • "()))((()"

여는 괄호와 닫는 괄호의 개수는 일치하지만 true를 반환한다.

세번째 시도

function solution(s){
 let answer = true;
    
 if(s.charAt(0) === ')' || s.charAt(s.length-1) === '(') answer = false; 

 const a = s.split('').filter((s) => s === '(').length;   
 const b = s.split('').filter((s) => s === ')').length; 
    
 if(a !== b) answer = false;
    
 let cntOpen = 0;
    
 for(let i = 0; i < s.length; i++) {
     if(s[i] === '(') cntOpen++;
     else cntOpen--;
        
     if(cntOpen < 0) answer = false;
 }
    
 return answer;
}

마지막으로 연속되는 여는 괄호의 수를 세서 닫는 괄호의 개수가 더 많을 시 false를 반환하게 만드니 통과를 받았다.

작은 문제들로 나눠서 해결하니 속도도 빠르고 내 머리가 감당할 수 있을만한 문제가 주어지게 되어서 나름 빠르게 풀 수 있었다..!

이런 접근으로 푸는 것도 좋은 것 같다. 나는 알고리즘 문제 푸는게 항상 느려서 고민이었는데 이런식으로 푸는 것을 더 연습해야겠다. 

반응형