오늘 문제는 스택의 대표 문제이죠. 유효한 괄호 찾기 문제입니다.
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Constraints:
1 <= s.length <= 104
s
consists of parentheses only '()[]{}'
.이 문제는 문자열 s
가 주어 졌을 때, s
에 있는 괄호들이 유효하게 구성되어 있는지를 파악해야 하는 문제입니다.
괄호가 유효하다는 것은 열린 괄호가 있으면 닫힌 괄호가 있어야 합니다. 즉, 열린 괄호와 닫힌 괄호가 1쌍으로 구성되어야 합니다. 또한 다른 괄호로 쌍을 이루는 것이 아닌 같은 형태의 괄호로 쌍을 이뤄야 합니다.
그럼, 문제에 차근차근 접근 해보겠습니다.
s
가 주어지고 s
는 '()[]{}'
의 괄호 들로만 구성되어 있습다.s
의 길이는 1부터 이다. 즉 빈 문자열은 주어지지 않는다는 것을 의미합니다.이 문제가 스택의 대표 문제인것은 알지만 왜 그런것인지, 다른 문제들처럼 처음 문제를 풀 때 생각하는 흐름대로 접근해보도록 하겠습니다.
우선, 직관적으로 생각해보았습니다. 소괄호, 중괄호, 대괄호가 모두 있지만 소괄호만을 가지고 단순화 해서 생각해보겠습니다.
()() -> valid
)( -> invalid
)() -> invalid
(())() -> valid
()(())() -> valid
위 예시들을 통해 확인할 수 있는 특징은 다음과 같습니다.
그렇다면, 여는 괄호가 있으면 1, 닫는 괄호가 있으면 -1로 지정해서 한다면 해결할 수 있을까요?
이렇게 한다면 2가지 특징은 해결할 수 있습니다. 문자열 s
로부터 반복문들 돌면서 최종 값이 0이 나오면 1번은 해결하게 되는 것이고, 반복문을 도는 중간에 음수가 나오면 여는 괄호로 시작했다는 것을 의미하기 때문에 False를 반환하면 됩니다.
이렇게 진행하면 해결될 것으로 보입니다. 하지만, 이것은 문자열 s
에 소괄호만 있다고 단순화 했을 때에 적용가능한 문제입니다.
한 번 확장을 해서 생각해보겠습니다.
(] -> +1 -1 == 0 -> invalid!!
즉, 종류에 따라서 다르게 계산을 해야 합니다.
(()){}[[]] -> (: 1 + 1 -1 -1 = 0
-> {: 1 - 1 = 0
-> [ : 1 + 1 - 1 -1 = 0
-> valid!!
이렇게 괄호의 종류에 따라 +1, -1 계산해서 0이 되기만 한다면 가능할까요?
(([{{}}))] -> (: 1 + 1 -1 -1 = 0
-> {: 1 + 1 -1 -1 = 0
-> [ : 1 - 1 = 0
-> valid???
해당 예시의 모든 괄호의 값은 0이 나왔습니다. 그러나, 유효한 괄호이지는 않습니다.
즉, 괄호의 종류별로 계산하는 것도 중요하지만, 각 괄호들의 순서도 중요하다는 것을 알 수 있습니다.
마지막에 들어온 괄호가 닫히기전에 다른 괄호로 닫아버리면 안되는것입니다. → LIFO!!!
이것을 통해 스택 자료 구조를 사용하면 된다는 것을 알 수 있습니다.
이제 코드를 설계해볼까요?
코드 설계
문자열 s
의 반복문을 돌면서 열린 괄호 ‘( { [’ 가 나오면 스택에 push하고 닫힌 괄호가 나오면 스택의 마지막 값과 짝이 맞는지 확인하고 맞으면 pop(), 짝이 맞지 않으면 False를 반환하면 됩니다. 이렇게 진행하고 최종적으로 스택이 비어있으면 True, 비어있지 않다면 False를 반환하면 됩니다.
스택의 Push와 Pop메서드의 시간복잡도는 이므로 반복문의 만큼의 시간 복잡도가 나올것으로 예상됩니다.
설계 내용을 바탕으로 코드를 구현해보겠습니다.
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for p in s:
if p == '(':
stack.append(')')
elif p == '{':
stack.append('}')
elif p == '[':
stack.append(']')
elif not stack or stack.pop() != p: # 스택이 비어있거나 짝이 맞지 않는것
return False
return not stack
코드 설명:
이 코드는 LIFO
방식의 스택 자료 구조를 활용하여 괄호의 유효성을 검사합니다.
s
의 각 문자를 순회하면서 열린 괄호가 나오면 스택에 해당 괄호의 짝을 저장합니다.'('
, '{'
, '['
이 나오면 스택에 각 괄호의 닫는 괄호 ')'
, '}'
, ']'
를 추가합니다. 이 방식으로 스택에는 닫히는 괄호들만 저장되며, 여는 괄호와 닫는 괄호의 짝이 맞는지 확인할 수 있습니다.not stack
) 현재 괄호와 짝이 맞지 않는다면 False
를 반환합니다. 이때 괄호의 쌍이 올바르지 않다는 의미이므로 유효하지 않은 괄호입니다.True
를 반환하고, 스택에 값이 남아있다면 False
를 반환합니다. 즉, 스택이 비어 있으면 모든 괄호가 올바르게 짝을 이뤘다는 의미가 됩니다.시간복잡도:
결과:
https://leetcode.com/problems/valid-parentheses/submissions/1445812606
이 문제는 스택 자료 구조를 효과적으로 사용하여 해결할 수 있는 대표적인 문제로, LIFO
원리를 이용해 괄호의 짝을 맞추고 유효성을 판단할 수 있습니다. 열린 괄호는 스택에 추가하고, 닫힌 괄호는 스택의 상단과 짝을 비교함으로써 간단하고 효율적인 코드로 구현할 수 있었습니다. 비록 해당 문제가 스택 자료 구조를 활용하는 대표 문제인것은 알고 있었지만, 지금은 학습하는 단계이기 때문에 기존의 다른 문제들처럼 차근차근 단계를 밟아가며 생각을 해보았습니다.
이 문제를 통해 문자열 순회와 스택을 활용한 조건 확인의 중요성을 확인할 수 있었으며, 괄호와 같이 짝을 이루어야 하는 문제들에서 스택을 사용해 시간 복잡도를 최소화하는 패턴을 익힐 수 있었습니다.
전체 코드는 다음 링크에서 확인할 수 있습니다.
읽어주셔서 감사합니다!!
오늘도 화이팅!