문제 링크
문제 설명
- 문자 '()', '()', '{), '}', '[]' 및 '[]'만 포함된 문자열이 주어지면 입력 문자열이 유효한지 확인합니다.
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
풀이 전략
- 유효한 문자열에는 균형 잡힌 괄호가 올바르게 정렬되어 있어야 합니다.
- 스택을 사용하면 "마지막에, 먼저"(LIFO) 원칙에 따라 각 마감 브래킷을 가장 최근에 일치하지 않는 오프닝 브래킷과 일치시킬 수 있습니다.
class Solution:
def isValid(self, s: str) -> bool:
stack = [] # 1. 괄호를 저장할 스택
bracket_map = {')': '(', '}': '{', ']': '['} # 2. 닫는 괄호와 여는 괄호의 매핑
for char in s: # 3. 문자열의 각 문자에 대해 반복
if char in bracket_map: # 4. 닫는 괄호인지 확인
top_element = stack.pop() if stack else '#' # 5. 스택에서 가장 최근에 추가된 요소를 꺼냄
if bracket_map[char] != top_element: # 6. 매칭되는 여는 괄호가 있는지 확인
return False # 7. 올바르지 않으면 False 반환
else:
stack.append(char) # 8. 여는 괄호라면 스택에 추가
return not stack # 9. 스택이 비어 있으면 True, 아니면 False
코드 분석
- 스택 초기화:먼저 빈 리스트
stack을 초기화합니다. 이 스택은 여는 괄호를 추적하는 데 사용됩니다.
stack = []- 괄호 대응 맵 정의:이 딕셔너리
bracket_map은 닫는 괄호(), }, ])에 해당하는 여는 괄호((, {, [로 맵핑을 정의합니다. 이 맵은 나중에 닫는 괄호가 등장할 때 대응되는 여는 괄호가 맞는지 확인하는 데 사용됩니다.
bracket_map = {')': '(', '}': '{', ']': '['}- 문자 순회:문자열
s의 각 문자를 차례로 순회하면서 다음과 같은 작업을 수행합니다.
for char in s:- 닫는 괄호 처리:
- 만약 현재 문자가 닫는 괄호라면 (
), }, ]), 스택의 맨 위 요소(top_element)를 확인합니다.
- 스택이 비어 있으면
#를 대신 사용하여 불일치를 의미합니다.
bracket_map[char]와 top_element를 비교하여 일치하지 않으면 False를 반환합니다. 이는 잘못된 괄호 구조임을 의미합니다.
if char in bracket_map:
top_element = stack.pop() if stack else '#'
if bracket_map[char] != top_element:
return False- 여는 괄호 처리:
- 만약 여는 괄호라면, 스택에 추가하여 추후 닫는 괄호가 나왔을 때 올바른 짝을 찾을 수 있도록 합니다.
else:
stack.append(char)- 스택 확인 후 결과 반환:
- 문자열
s를 모두 순회한 후 스택이 비어 있으면 모든 괄호가 올바르게 짝지어졌다는 의미이므로 True를 반환합니다.
- 스택에 남은 요소가 있으면 올바르지 않은 괄호 구조이므로
False를 반환합니다.
return not stack
