.leetcode(20. Valid Parentheses)

문제

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

문제 풀기 전

1. 이렇게 괄호 짝 맞추는거는 보통 stack을 쓰면되더라.
2. 처음에 stack에 아무것도 없을때는 [{( 만 허용되고 젤 위에 들어간 기호에 따라 추가적으로 닫는 기호만 더 허용된다는 룰을 갖고 만들어보자.

직접 푼 풀이

소요시간: //9분(20:30 ~ 20:39)

class Solution {
    public boolean isValid(String s) {
        Set<Character> basicAllowed = new HashSet();

        LinkedList<Character> stack = new LinkedList<>();
        for(int i=0; i<s.length(); i++) {
            Character sign = s.charAt(i);
            Character top = stack.peek();

            if (top == null) {
                if (sign == '(' || sign == '{' || sign == '[') {
                    stack.push(sign);
                } else {
                    return false;
                }
            } else if (top == '[') {
                if (sign == '(' || sign == '{' || sign == '[') {
                    stack.push(sign);
                } else if (sign == ']') {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (top == '{') {
                if (sign == '(' || sign == '{' || sign == '[') {
                    stack.push(sign);
                } else if (sign == '}') {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (top == '(') {
                if (sign == '(' || sign == '{' || sign == '[') {
                    stack.push(sign);
                } else if (sign == ')') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        return stack.size() == 0;
    }
}

#위와 원리는 같지만 코드 정리함
class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for(int i=0; i<s.length(); i++) {
            Character sign = s.charAt(i);
            Character top = stack.peek();

            if (sign == '(' || sign == '{' || sign == '[') {
                stack.push(sign);
            } else {
                if (top == null) {
                    return false;
                } else if ((top == '[' && sign == ']')
                    || (top == '{' && sign == '}')
                    || (top == '(' && sign == ')')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        return stack.size() == 0;
    }
}

느낀점

1. 역시 stack이 맞았구나.
2. 솔루션도 stack을 써서 풀었다. 원리는 같다 코드형식만 다를뿐이다.

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)