본문 바로가기

알고리즘/백준

[9012]괄호

1. 문제

www.acmicpc.net/problem/9012

 

9012번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고

www.acmicpc.net

2. 접근 방법

1)스택을 이용해서 '('이면 스택에 넣고 ')'이면 스택에서 뺀다. 만약 '('이 나와서 빼려했는데 이미 스택이 비어있거나, 모든 괄호를 다 봤는데 아직 스택이 비어있지 않으면(닫히지 않은 괄호들이 있음) 올바르지 않은 문자열이다.

 

3. 실수했던 부분 & 처음 알았던 부분

1)stack에서 pop할때만 생각하지 말고, for문을 나왔을 때 스택에 값이 남아있는지까지 확인할 것!

 

4. 코드

더보기
#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main() {
	int T;
	string s;
	cin >> T;

	while(T--) {
		stack<int> st;
		bool flag = true;
		cin >> s;
		for(int i=0;i<s.size();i++) {
			if(s[i] == '(')
				st.push(1);
			else if(st.empty()) { 
				flag = false;
				break;
			}
			else st.pop();
		}
		if(!flag || !st.empty()) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
	return 0;

}

'알고리즘 > 백준' 카테고리의 다른 글

[18111] 마인크래프트(python)  (0) 2021.08.01
[1654] 랜선 자르기(python)  (0) 2021.07.26
[2805]나무자르기(C++)  (0) 2020.12.08
[11048] 이동하기(C++/DP)  (0) 2020.12.07
[2468]안전 영역(C++)  (0) 2020.10.18