[LeetCode- Ch6. 큐와 스택] 2. 유효한 괄호

 

https://leetcode.com/problems/valid-parentheses/

 

1. 여는 괄호가 있을 때와 없을 때로 구분하기

: 여는 괄호 있으면 현재 값을 확인해 여는 괄호와 맞는 닫는 괄호면 여는괄호 삭제

 

2. 그 외의 경우엔 넣기

 

3. 스택이 비었을 때 true 반환

 

 

import java.util.Stack;

public class Solution {
    public static boolean isValid(String s) {
        //open일때 close일 때
        //모두 비었을 때 -> true;
        int n = s.length();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            System.out.println(i + " " +s.charAt(i)+" "+stack.size());
            if (stack.isEmpty()) {
                if (s.charAt(i) == '}' || s.charAt(i) == ')' || s.charAt(i) == ']') {
                    System.out.println(1);
                    return false;
                }else{
                    stack.push(s.charAt(i));
                    System.out.println(3 + " " + stack.size()+" "+stack.peek());
                }
            }
            else if(stack.peek() == '{' ||stack.peek() == '[' ||stack.peek()=='('){
                System.out.println(i + " " + stack.size()+" "+stack.peek());

                if (stack.peek() == '{' &&s.charAt(i) == '}' ) {
                    System.out.println(2);
                    stack.pop();
                }
                else if (stack.peek() == '[' && s.charAt(i) == ']' ) {
                    System.out.println(2);
                    stack.pop();
                }
                else if (stack.peek() == '('&&s.charAt(i) == ')') {
                    System.out.println(2);
                    stack.pop();
                }else{
                stack.push(s.charAt(i));
                System.out.println(3 + " " + stack.size()+" "+stack.peek());
            }

            }

        }

        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }
}

---

+) 세련된 풀이

1. 스택 이용

2. 스택 이용

3. Map과 스택 이용

import java.util.*;

public class ValidParentheses {

      public boolean solve_1(String s) {
        Stack<Character> stack = new Stack<>();
    
        for(int i = 0; i<s.length(); i++) {
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
                stack.push(s.charAt(i));
            else if(s.charAt(i) == ')' && !stack.empty() && stack.peek() == '(')
                stack.pop();
            else if(s.charAt(i) == ']' && !stack.empty() && stack.peek() == '[')
                stack.pop();
            else if(s.charAt(i) == '}' && !stack.empty() && stack.peek() == '{')
                stack.pop();
            else
                return false;
        }
        return stack.empty();
    }
	
}

	public static boolean solve(String str) {
		Stack<Character> stack = new Stack<>();
		for(char c: str.toCharArray()) {
			System.out.println("c: "+c);
			if(c=='(') {
				stack.push(')');
			}else if(c=='[') {
				stack.push(']');
			}else if(c=='{') {
				stack.push('}');
			}else if(stack.isEmpty()|| stack.pop() != c) {
				return false;
			}
			
		}
		return stack.isEmpty();
	}

	public static boolean isValid_map(String str) {
		Map<Character, Character> map = new HashMap<>();
		map.put('{', '}');
		map.put('(', ')');
		map.put('[', ']');
		Stack<Character> stack = new Stack<>();
		
		for(int i=0; i<str.length(); i++) {
			char c = str.charAt(i);
			if(map.containsKey(c)) {
				stack.push(c);
			}else if(map.containsValue(c)) {
				if(!stack.isEmpty() && map.get(stack.peek())==c) {
					stack.pop();
				}else {
					return false;
				}
			}
		}
		return stack.isEmpty();
	}

---

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c:s.toCharArray()){
            if(c=='('||c=='{'||c=='['){
                stack.push(c);
            }else if(!stack.isEmpty()&&c==')' &&stack.peek()=='('){
                stack.pop();
            }else if(!stack.isEmpty()&&c=='}' &&stack.peek()=='{'){
                stack.pop();
            }else if(!stack.isEmpty()&&c==']' &&stack.peek()=='['){
                stack.pop();                
            }else return false;
        }
        return stack.isEmpty()?true:false;
    }
}