[LeetCode] 20. Valid Parentheses

20. Valid Parentheses

LeetCode

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

문자열 s가 '(', ')', '{', '}', '[', ']' 문자들로만 이루어져 있을 때, 입력된 문자열이 유효한지(Valid) 판별하세요.

입력 문자열은 다음 조건들을 만족해야 유효합니다:
1. 열린 괄호는 반드시 동일한 종류의 괄호로 닫혀야 합니다.
2. 열린 괄호는 반드시 올바른 순서대로 닫혀야 합니다.
3. 모든 닫힌 괄호는 그에 대응하는 동일한 종류의 열린 괄호가 있어야 합니다.

 

Example

Input: s = "()"
Output: true

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

Input: s = "([)]"
Output: false

---

1. 문제 요구사항 분석

이번 문제는 괄호 쌍이 맞는지 체크하는 문제

 

2. 접근 전략

😄 Stack 사용: LIFO last in first out 문제 - 시간복잡도 O(n)

참고사항 : Java에서는 Stack 클래스보다 ArrayDeque가 더 성능 좋음

import java.util.*;

class Solution {

	public boolean isValid(String s) {

		if (s == null || s.length() == 0) return true;

		Deque<Character> stack = new ArrayDeque<>();

		for (char c: s.toCharArray()) {
			if (c == '(' || c == '[' || c == '{') {
				stack.push (c); // 맨 뒤 데이터
			} else if (c == ')' || c == ']' || c == '}') {
				if (stack.isEmpty()) return false;
				char e = stack.pop(); // 맨 앞 데이터

				if (c == ')' && e != '(') return false;
				if (c == ']' && e != '[') return false;
				if (c == '}' && e != '{') return false;
			} else {
				continue;
			}
		}
		
		return stack.isEmpty();
	}
}