기록하는 습관을 들이자

[ leetcode ] Valid Parentheses 본문

알고리즘/Leetcode

[ leetcode ] Valid Parentheses

myeongmy 2021. 1. 20. 21:58
반응형

 

문제

leetcode.com/problems/valid-parentheses/

 

Valid Parentheses - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

문제 풀이

 

주어진 괄호 문자열이 올바른 문자열인지 판단하는 간단한 알고리즘입니다. "스택" 자료구조를 사용하여 문제를 해결하면 됩니다. 문자열에서 등장할 수 있는 괄호 유형에 대해 번호를 매긴 후, 여는 괄호가 등장할 때는 해당 괄호에 대응하는 번호를 스택에 push 해주고, 닫는 괄호가 등장할 때는 현재 스택의 맨 위에 저장된 여는 괄호가 현재 닫는 괄호와 쌍이 일치하는지를 판단하여 일치하지 않으면 false를 리턴, 일치하면 스택의 맨 위 요소를 pop 해주면 됩니다.

 

주의할 점은 문자열을 for문을 이용하여 다 탐색을 한 후 마지막에 스택이 비어있는지 여부를 판단해주어야 합니다. 문자열을 다 탐색했는데 스택에 아직 element가 남아있다면 그것은 올바른 괄호 문자열이 아니기에 false를 리턴해주어야 합니다.

 

 

코드

class Solution {
    public boolean isValid(String s) {
        Stack<Integer> st = new Stack<Integer>();
        
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == '('){
                st.push(1);
            }else if(s.charAt(i) == '['){
                st.push(2);
            }else if(s.charAt(i) == '{'){
                st.push(3);
            }else if(s.charAt(i) == ')'){
                if(st.empty() || st.peek() != 1)
                    return false;
                st.pop();
            }else if(s.charAt(i) == ']'){
                if(st.empty() || st.peek() != 2)
                    return false;
                st.pop();
            }else if(s.charAt(i) == '}'){
                if(st.empty() || st.peek() != 3)
                    return false;
                st.pop();
            }
        }
        
        if(!st.empty())
            return false;
        
        return true;
    }
}
반응형
Comments