알고리즘 문제/Leetcode
[Leetcode] 20. Valid Parentheses
햄과함께
2023. 4. 10. 21:26
320x100
문제 : https://leetcode.com/problems/valid-parentheses/description/
'(', ')', '{', '}', '[', ']' 문자만 포함하는 문자열 s가 주어집니다. 입력 문자열이 유효한지 여부를 판단하세요.
입력 문자열이 유효한 경우는 다음과 같습니다.
열린 괄호는 같은 종류의 괄호로 닫혀야 합니다.
열린 괄호는 올바른 순서로 닫혀야 합니다.
각 닫는 괄호는 동일한 유형의 열린 괄호와 대응 되어야 합니다.
문자열을 탐색하면서 열린 괄호가 나오면 스택에 넣습니다.
닫힌 괄호가 나오는 경우 스택의 탑에 있는 괄호와 대응되지 않거나 스택이 비어있을 땐 유효한 경우가 아닙니다.
스택의 탑에 있는 열린 괄호와 탐색 중인 닫힌 괄호가 대응된다면 스택의 탑에 있는 문자를 하나 제거하고 탐색을 재개합니다.
모든 문자열을 탐색했을 때 스택이 비어있는 경우 유효한 경우가 됩니다.
시간복잡도는 O(N).
소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/20.%20Valid%20Parentheses.cpp
320x100