[Leetcode/JAVA] 02. Valid Parentheses

📄 Valid Parentheses

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

 

 

문제 분석

문자열이 주어졌을 때 입력 문자열이 유효한지 확인하는 문제이다.

• 조건 1) 열린 괄호는 같은 유형의 괄호로 닫아야 한다.
• 조건 2) 열린 괄호는 올바른 순서로 닫아야 한다.
• 조건 3) 모든 닫힌 괄호에는 같은 유형의 열린 괄호가 대응된다.

 

접근 방법

 스택 을 이용하여  for 문을 통해 문자열을 순회하며 열린 괄호를 만나면 스택에 삽입할 것이다.

문자열을 순회하며 닫힌 괄호를 만나면 스택에서 짝을 이루는 괄호가 있는지 확인한다.

문자열을 순회한 후, 스택이 비어있다면 유효한 괄호이고 아니라면 유효하지 않은 괄호이다.

 

문자열의 크기를 $N$이라고 할 때, 시간 복잡도는 $O(N)$이다.

 

코드 설계

# 괄호를 저장할 스택 stack 을 선언한다.

# 문자열을 문자형 배열로 변환하여 for 문을 실행하여 유효 여부를 확인한다.

# 열린 괄호라면 스택에 삽입한다.

# 닫힌 괄호라면 자신과 짝을 이루는 괄호가 존재하는지 확인한다.

 

 

코드 구현

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

        return stack.isEmpty();
    }
}