코딩테스트 문제 (2) - 유효한 괄호

이 문제는 괄호 "(,),{,},[,]" 로 이루어진 string이 입력으로 들어왔을 때, 괄호의 여는 곳과 닫는 곳이 문맥 상 일치하는지 묻는 문제로 대표적인 스택 문제입니다. 테스트 케이스를 한 번 살펴보죠.

문제

1. '{}(){}' => True, 2. '{()}[]' => True, 3. '{{)}[}' => False, 4. '(([]))' => True

풀이

스택 문제라고 언급했는데, 스택을 어떻게 이용해야 할까요? 스택은 마지막 원소가 추출되니 '[', '(', '{' 같이 여는 괄호를 스택에 순서대로 넣어두고 ']', ')', '}' 가 들어오면 스택에서 pop해서 매칭이 되는지 확인하면 될 것 같습니다. 그리고 마지막에 스택에 원소가 남아 있으면, 매칭되는 닫는 괄호가 입력에 없는 것이므로 False를 return하면 되겠네요.

kaggle.com 의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 괄호 매칭되는 문제는 스택으로!
• 난이도: 하

참조

• <파이썬 알고리즘 인터뷰>, p245-246
• leetcode.com/problems/valid-parentheses/