algospot 짝이 맞지 않는 괄호(문제 ID: BRACKETS2) c++

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/BRACKETS2

algospot.com :: BRACKETS2

( ) { } [ ] 이렇게 세 종류의 괄호를 나열한 문자열이 주어졌을때 해당 문자열이 짝이 맞는지를 확인하는 문제이다.

여기서 짝이 맞는다는 표현은 다음 세가지 조건을 모두 지켰을 경우를 말한다.

- ( 는 ) 와, { 는 } 와, [ 는 ]와 짝을 이루어야만 한다.

- 모든 괄호 쌍은 먼저 열린 뒤 닫힌다.

- 한 괄호 쌍이 다른 괄호쌍과 서로 '교차해' 있으면 안된다. 이 정의에 의하면 [ ( ] ) 는 짝이 맞지 않는 경우이다.

 

스택을 이용하면 다음과 같은 방식으로 문제를 풀 수 있다.

문자열을 순회하면서 열린괄호면은 스택에 넣는다.

닫힌 괄호면 현재 스택의 탑에 있는것과 대응한다면 스택의 탑을 pop하고 대응하지 않는다면 false를 리턴한다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/19.%20QueueStackDeque/BRACKETS2.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2