[Algorithm/java] Valid Parenthese

1865 단어 algorithmalgorithm

Problem

Input : "{[]}"
Output : true

Input : "([)]"
Output : false

Input : "(){}[]"
Output : true

Input : "(]"
Output : false

Solution

  • Stack 이용
    1. 오픈 괄호들 먼더 스택에 넣는다.
    1. 클로즈 괄호들이 나오면 뺀다.
    1. 최종으로 stack에 남아있는지를 확인한다.
  • Map, Switch Case이용

Code

package stack_queue;

import java.util.*;

public class ValidParentheses {
    
    public static void main(String[] args){
        //String exp="{({})}";
        String exp = "([)]";
        System.out.println(isValid(exp));
    }
    
    public static boolean isValid(String s){
        //1 error check (괄호는 늘 쌍으로 이루어지기에 홀수 갯수라면 무조건 false 리턴)
        if(s.length()%2 != 0) return false;
        
        Stack<Character> stack = new Stack<>();
        
        //2 경우에 따라 나눠줄 수 있도록 반복문 돌려서 체크
        for(int i=0; i<s.length(); i++){
            switch(s.charAt(i)){
                case ')':
                    if(!stack.empty() && stack.peek()=='(') stack.pop();
                    break;
                    
                case '}':
                    if(!stack.empty() && stack.peek()=='{') stack.pop();
                    break;
                    
                case ']':
                    if(!stack.empty() && stack.peek()=='[') stack.pop();
                    break;
                    
                default:
                    stack.push(s.charAt(i));
                    break;
                    
            }
        }
        
        return stack.empty();
    }
}

좋은 웹페이지 즐겨찾기