[Leetcode] 20. Valid Parentheses

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

---

'(', ')', '{', '}', '[', ']' 문자만 포함하는 문자열 s가 주어집니다. 입력 문자열이 유효한지 여부를 판단하세요.

입력 문자열이 유효한 경우는 다음과 같습니다.

열린 괄호는 같은 종류의 괄호로 닫혀야 합니다.

열린 괄호는 올바른 순서로 닫혀야 합니다.

각 닫는 괄호는 동일한 유형의 열린 괄호와 대응 되어야 합니다.

---

문자열을 탐색하면서 열린 괄호가 나오면 스택에 넣습니다.

닫힌 괄호가 나오는 경우 스택의 탑에 있는 괄호와 대응되지 않거나 스택이 비어있을 땐 유효한 경우가 아닙니다.

스택의 탑에 있는 열린 괄호와 탐색 중인 닫힌 괄호가 대응된다면 스택의 탑에 있는 문자를 하나 제거하고 탐색을 재개합니다.

모든 문자열을 탐색했을 때 스택이 비어있는 경우 유효한 경우가 됩니다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/20.%20Valid%20Parentheses.cpp