[LeetCode] Valid Parentheses

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

문제 파악

1. 입력된 문자열이 올바르게 작성되어있는지 판단
2. 괄호가 열린채로 끝나거나 괄호의 짝이 맞지 않으면 false
3. 괄호가 닫혀있고 괄호의 짝이 맞으면 true

접근 방법

1. String을 CharArray.로 변환
2-1. 닫힌 괄호가 들어왔다
			1) 배열이 비어있는지 확인한다 => 열린괄호가 있는지 확인
			2) 열린괄호가 있다면 닫힌 괄호와 짝인지 확인
			3) 같은 괄호면 계속 탐색, 열린괄호면 false
3. 열린 괄호가 들어오면 stack에 추가한다.
4. 만약 다 탐색 했는데 stack의 크기가 0이 아니면 false=> 괄호의 짝이 안 맞음

**!! ca[0] ==']' or ca[ca.length-1] ==']'로 처음에 걸러줄 수 있지만 크게 차이는 없다.**
   단, ca[ca.length-1] ==']'이 ca[0] ==']'보다는 효율 적이다.
   => ca[0] ==']'는 처음을 거르는 거지만 ca[ca.length-1] ==']'는 마지막까지 탐색하는 것을 거를 수 있다.

💡 실패한 사례
1. testcase “[” : 오류 발생 ⇒ 마지막 까지 for가 돌았을 때 stack이 비어있는지 확인하지 못 하였다. ⇒ for문 이후 if(!stack.isEmpty()) istrue=false 를 통해 마지막에 스택이 비어있는지 확인
2. testcase “]” : 오류 발생 ⇒ 스택이 비어있는데 stack.peek()를 할 경우 오류가 발생하는 것을 확인하지 못 하였다. ⇒ stack.peek() 이전 stack.isEmpty()를 통해 stack이 비어있는지 우선 확인

코드 구현

class Solution {
    public boolean isValid(String s) {
        char[] ca = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        stack.add(ca[0]);
        boolean istrue = true;
        for (int i = 1; i<ca.length; i++) {
            char c = ca[i];
            if (c == '}') {
                if (stack.isEmpty()){
                    istrue = false;
                    break;
                }
                if (stack.peek() == '{') {
                    stack.pop();
                } else {
                    istrue = false;
                    break;
                }
            } else if (c == ']') {
                if (stack.isEmpty()){
                    istrue = false;
                    break;
                }
                if (stack.peek() == '[' ) stack.pop();
                else {
                    istrue = false;
                    break;
                }
            } else if (c == ')') {
                if (stack.isEmpty()){
                    istrue = false;
                    break;
                }
                if (stack.peek() == '(' ) stack.pop();
                else {
                    istrue = false;
                    break;
                }
            } else stack.push(c);
        }
        if(!stack.isEmpty()) istrue=false;
        return istrue;
    }
}

배우게 된 점

💡 Deque<Character> deque= new ArrayDeque<>(); 를 통해 stack, queue를 구현할 수 있다는 것을 배웠다.