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

문제

나의 풀이

1차 풀이

프로그래머스 Lv.1의 문제 중에 비슷한 문제를 풀었어서 보자마자 바로 코드를 짰다.
1. stack 사용
2. '()'의 경우 pop하여 삭제해준다.
3. 그 이외의 경우에는 push한다.
4. 만약 ')('이 발견되는 경우 즉시 break 한다. -> 올바르지 않은 괄호

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        char[] brackets = s.toCharArray();
        
        for(char bracket : brackets) {
            if(stack.isEmpty() || stack.peek()==bracket) {
                stack.push(bracket);
            }else{
                if(bracket=='(') break;
                else stack.pop();
            }
        }
        
        return stack.isEmpty()? true : false;
    }
}

그런데 보다싶이 효율성 테스트에서 시간초과가 떴다. 이럴수가 ..

2차 풀이

1. 괄호의 수가 홀수면 맞아 떨어질 수가 없으므로 바로 false 리턴.
2. stack을 사용하지 않고 int를 사용한다.
   => (를 +1, )를 -1라 했을 때, 모든 괄호를 더하면 합이 0이 되어야 true.
3. 최근 괄호가 ')'인데 '('가 들어오면 break : cntLeft<0-> 올바르지 않은 괄호
   => 이 조건이 있어야 )()()( 와 같은 경우를 구별해낼 수 있다.
   

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        
        char[] brackets = s.toCharArray();
        if(brackets.length%2!=0) return false;
        int cntLeft = 0;
        
        for(char bracket : brackets) {
            cntLeft += bracket==')'?-1:1;
            if(cntLeft<0) break;
        }
        
        return cntLeft==0? true:false;
    }
}

바로 통과했다 ~!