Valid Parentheses1 [Easy] Leetcode | 20. Valid Parentheses | String, Stack - 문제 스택의 대표적인 문제인 괄호 검사 알고리즘 문제이다. 괄호로 이루어진 문자열이 주어지는데 이 문자열 속 괄호들이 쌍에 맞으며 순서 또한 맞는지 검사하는 문제이다. - 풀이 스택의 LIFO (Last In First Out) 성질을 이용하여 순서와 쌍을 검사한다. 대략적인 알고리즘은 문자열의 크기만큼 루프를 돌면서 열린 괄호는 모두 스택에 저장한다. 따라서 시간 복잡도는 O(n)이 될 것이며 최악의 경우 스택에 n개 모두 저장하므로 공간 복잡도는 O(n)이 될 것이다. 만약 닫힌 괄호( ')', '}', ']' ) 가 나온다면 무조건 스택의 top(마지막에 저장한 괄호)과 쌍이 맞아야 하므로 top이 쌍이 맞지 않다면 false를 반환하며 쌍이 맞다면 top의 요소를 pop한다. 이 과정을 반복하.. 2020. 1. 29. 이전 1 다음
