[프로그래머스] 올바른 괄호 (Lv2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12909

---

고민 1. 올바른 괄호의 조건은?

• 여는 괄호 '('로 시작한다.
• 여는 괄호 '('와 닫는 괄호 ')'의 개수는 같아야 한다.
• 닫는 괄호 ')'로 끝나야 한다.

고민 2. 어떤 알고리즘을 사용할까?

올바른 괄호인지 검사하는 쉬운 방법은 닫는 괄호를 만나면
그 앞쪽에서 가장 가까운 여는 괄호와 짝을 지어 전체 두 괄호의 개수가 동일한지 확인하면 된다.
자료 구조 중 스택은 후입선출, 큐는 선입선출이므로 스택을 이용하면 된다.

1. 문자열의 시작과 끝이 올바르지 많다면 false로 종료
2. 여는 괄호를 만나면, 스택에 1 push
3. 닫는 괄호를 만나면, 스택이 비었는지 확인 -> 비었으면 false로 종료
4. 스택이 비어있지 않다면 스택에서 1 pop
5. 2~4를 반복한다
6. 문자열 순회 후, 스택의 크기가 0인지 확인한다 -> 0이 아니면 짝이 맞지 않음 false로 종료
7. 모두 통과했다면 true !

import java.util.Stack; 

class Solution {  
    boolean solution(String s) {
        Stack<Integer> stack = new Stack<>(); 
        
        // 시작과 끝이 올바르지 않음
        if(s.charAt(0)==')'|| s.charAt(s.length()-1)=='(') return false;
        
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(')
                stack.push(1);
            else{
                if(stack.empty()) return false; // 스택이 비어있으면 짝이 없는것임
                stack.pop();
            }       
        }
        
        // 모두 짝지어졌는지 확인
        if(stack.size()!=0) return false; 
        
        return true;
    }
}

---

최종코드

GitHub Java-algorithm-practice/프로그래머스/lv2/12909. 올바른 괄호/

import java.util.Stack; 

class Solution {  
    boolean solution(String s) {
        Stack<Integer> stack = new Stack<>(); 
        
        // 시작과 끝이 올바르지 않음
        if(s.charAt(0)==')'|| s.charAt(s.length()-1)=='(') return false;
        
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(')
                stack.push(1);
            else{
                if(stack.empty()) return false; // 스택이 비어있으면 짝이 없는것임
                stack.pop();
            }       
        }
        
        // 모두 짝지어졌는지 확인
        if(stack.size()!=0) return false; 
        
        return true;
    }
}