올바른 괄호 (시간복잡도 안에 들어오기만 한다면 시간을 조금 포기한 간단풀이도 때론 필요한 법 , 짝 이루기의 0)

https://school.programmers.co.kr/learn/courses/30/lessons/12909/solution_groups?language=java

프로그래머스

 

import java.util.*;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<s.length(); i++){
            //'(' 이면 push
            if(s.charAt(i)=='('){
                stack.push(s.charAt(i));
            }
            else{
                if(stack.isEmpty()){
                    answer = false;
                    break;
                }
                char c = stack.peek();
                //')' 이면 peek해서 ( 가 있나 
                if(c=='('){
                    //있으면 poll해서 ( 삭제
                    stack.pop();
                }
                else{
                    //없다면 false 리턴
                    answer = false;
                    break;
                }
            }
        }
        if(!stack.isEmpty()){
            answer=false;
        }
        return answer;
    }
}

최대한 시간을 짧게 가볼려고 중간에 특정 부분에서 break문 넣고 하다 보니 코드가 길어지고 가독성이 떨어지는 측면이 있다.

 

이렇게 해서 통과를 한번 시켜보고 시간적 이득을 좀 버리고 깔끔하게 짜보도록 해보았다.

import java.util.*;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='('){
                stack.push(s.charAt(i));
            }
            else{
                if(stack.isEmpty()){
                    stack.push(s.charAt(i));
                }
                else{
                    if(stack.peek()=='('){
                        stack.pop();
                    }
                }
            }
        }
        if(!stack.isEmpty()){
            answer = false;
        }
        return answer;
    }
}

 

stack에 무엇인가가 남아있는 순간 그건 정상적인 괄호들이 아니기에 처리해줬다.

 

 

다른 풀이:

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        int count = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            }
            if(s.charAt(i) == ')'){
                count--;
            }
            if(count < 0){
                break;
            }
        }
        if(count == 0){
            answer = true;
        }

        return answer;
    }
}

괄호 문제는 무조건 Stack이다를 떠올리지 않는 또 하나의 풀이이다.

'(' 와 ')' 는 짝을 이루어야 하고 특히 짝 순서 ( 가 먼저, )가 나중에 와야하기에 (를 +1 , ) 를 -1로 하면 된다.