★ solved.ac 난이도 : S4
(2021년 12월 29일 기준)
[문제 링크]
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
[문제 분석]
스택을 활용한 괄호 검사 문제
[풀이]
이 문제는, 괄호의 모양이 올바른지를 검사하는 문제입니다.
자료구조를 예습하면서 접하게 된 문제인데요,
여기에서 LIFO(후입 선출)의 스택을 사용했습니다.
그 이유는, 가장 가까운 거리에 있는 괄호끼리 서로 쌍을 이루어야 하기 때문입니다.
괄호 검사의 조건을 알려드리자면,
조건 1. 여는 괄호와 닫는 괄호의 개수가 같아야 함
조건 2. 같은 종류의 괄호에서 여는 괄호가 닫는 괄호보다 먼저 나와야 함
조건 3. 서로 다른 종류의 여는 괄호와 닫는 괄호가 서로 교차하면 안 됨
여기에서는 괄호가 소괄호 쌍만 나오기 때문에, 조건 3은 무시하셔도 됩니다.
(단, 중괄호나 대괄호 등 여려 종류의 괄호가 섞여서 나오게 된다면, 조건 3도 포함시켜야 합니다.)
그리고, 스택의 push 연산과 pop 연산을 구현하지 않고 top의 값만 적절히 조절해주면 풀 수 있습니다.
초기 상태에는 top을 -1로 정하고,
여는 괄호가 나왔을 때 +1, 닫는 괄호가 나왔을 때 -1씩 조절합니다.
만약 스택이 비어있을 때 닫는 괄호가 나온다면, 괄호 검사 오류이고(조건 1 또는 조건 2 위반),
최종적으로 스택이 비어있지 않아도 괄호 검사 오류입니다(조건 1 위반).
(자세한 내용은 아래의 소스를 참고해주세요~!)
[소스 코드]
만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)