C++:: 스택 활용 (수식의 괄호쌍)

참고 내용

https://blog.encrypted.gg/936

정의

수식의 괄호쌍이란?

EX) (()) ()(), 

> 괄호의 쌍이 예시와 같이 올바른지 판단하는 문제

 

괄호 쌍이 올바른지 판단하는 방법

주인장의 생각

열린 괄호 = '('    닫힌 괄호 = ')'

1. 열린 괄호가 닫힌 괄호보다 먼저 나와야 함
2. 열린 괄호가 있으면 닫힌 괄호가 반드시 따라와야 함

 

타인의 방법

• 안쪽부터 짝 맞추기
• 열린 괄호의 개수 = 닫힌 괄호의 개수

구현

배열 : 최대 N번 중간에 있는 원소의 삭제 발생 => O(N^2)

연결리스트 : O(N)

스택 : 닫힌 괄호는 가장 최근에 들어온 여는 괄호와 짝 지어 없애자

 

해결 방법

1. 여는 괄호가 나오면 스택에 추가

2. 닫는 괄호가 나올 경우

    2-1 스택이 비어 있으면 올바르지 않은 괄호 쌍

    2-2 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍

    2-3 스택의 top이 짝이 맞는 괄호일 경우 pop

3. 모든 과정을 끝낸 후 스택에 괄호가 남았으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍

 

 

예제

3986 좋은 단어

#include <bits/stdc++.h>
using namespace std;

int result = 0;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	string str;
	while(n--) {
		cin >> str;
		stack<int> S;
		int cntA = 0, cntB = 0;
		
		for(char c : str) {
			if(S.empty()) S.push(c);
			else if(S.top() != c) S.push(c);
			else S.pop();
		}
		if(S.empty()) result++;
	}
	cout << result;
}

처음에 복잡하게 생각해서 문자가 'A'와 'B'일 때를 나눠서 생각하다가

'아! 스택이 비어있는지 아닌지만 마지막에 검사하면 되겠다!' 싶어서

while문 마지막에 S.empty()를 검사하는 구문으로 처리했다.

 

기억할 점

S.top() : 스택이 비어있을 때 쓰면 오류 생김!