오늘은 9월 둘째주 월요일입니다. 벌써 9월이 된지 1주일이 지났군요,, 이제 논문작업이 좀 들어가서 코테 준비를 전념하기에는 힘들지만 꾸준히 진행하고는 있습니다. 오늘 문제는 스택 자료 구조 유형에서 가장 대표적인 괄호 문제입니다!
1. 오늘의 학습 키워드
- 괄호
2. 문제: 올바른 괄호
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예
| s | answer |
|---|---|
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
입출력 예 설명
입출력 예 #1,2,3,4
문제의 예시와 같습니다.
3. 나의 풀이
문제 이해 및 접근
이 문제는 스택 자료구조를 활용해 괄호가 올바르게 짝지어졌는지 확인하는 문제입니다. 문자열에서 ‘(’와 ‘)’의 짝이 맞아야 하며, 여는 괄호가 나왔을 때는 스택에 저장하고, 닫는 괄호가 나왔을 때는 스택에서 여는 괄호를 꺼내서 짝을 맞춥니다. 스택이 비어 있거나, 문자열을 모두 처리한 후에도 스택에 남은 여는 괄호가 있으면 잘못된 괄호입니다.
접근 방법
- 여는 괄호 '('가 나오면 스택에 넣습니다.
- 닫는 괄호 ')'가 나오면 스택에서 여는 괄호를 꺼냅니다. 이때 스택이 비어 있으면 잘못된 괄호입니다.
- 문자열을 모두 처리한 후, 스택이 비어 있으면 괄호가 올바르게 짝지어졌다고 판단하고
True를 반환합니다. 스택에 값이 남아 있으면False를 반환합니다.
코드 설명
from collections import deque
def solution(s):
stack = deque() # 스택을 사용하기 위해 deque 자료구조를 사용
for i in s: # 문자열 s를 한 글자씩 처리
if i == '(': # 여는 괄호가 나오면 스택에 넣음
stack.append(i)
else: # 닫는 괄호가 나오면
if not stack: # 스택이 비어 있으면 짝이 맞지 않으므로 False 반환
return False
else:
stack.pop() # 스택에서 여는 괄호를 꺼냄
# 문자열을 모두 처리한 후 스택이 비어 있으면 True, 남아 있으면 False
return True if not stack else False
풀이 과정
- 스택 사용: 문자열에서 여는 괄호 '('는 스택에 쌓고, 닫는 괄호 ')'는 스택에서 여는 괄호를 제거하는 방식으로 처리합니다.
- 예외 처리: 닫는 괄호가 나왔을 때 스택이 비어 있다면, 짝이 맞지 않는 괄호이므로 바로
False를 반환합니다. - 최종 결과: 문자열을 모두 처리한 후 스택이 비어 있어야만 괄호가 올바르게 짝지어졌다고 판단하고
True를 반환합니다.
시간 복잡도
이 코드는 문자열을 한 번 순회하므로 시간 복잡도는 입니다. 이때 n은 문자열의 길이입니다. 스택에 값을 넣고 빼는 연산은 이므로, 매우 효율적입니다.
마무리
이번 문제는 스택 자료구조를 활용하여 괄호의 짝을 맞추는 대표적인 문제였습니다. 스택의 기본적인 원리인 LIFO(Last In, First Out) 구조를 통해 여는 괄호를 쌓고, 닫는 괄호가 나오면 이를 짝지어 제거하는 방식으로 쉽게 해결할 수 있었습니다.
이 문제는 시간 복잡도 O(n)으로 매우 효율적이며, 스택을 사용한 괄호 문제의 기본적인 접근 방식을 연습하기에 좋은 문제입니다. 앞으로도 이러한 스택 문제를 많이 풀어보면, 더 복잡한 자료구조 문제도 자연스럽게 해결할 수 있는 기반이 될 것입니다.
비슷한 문제로 백준 9012번이 있습니다.
읽어주셔서 감사합니다.
더 나은 개발자가 될거야!!
