알고리즘/백준
백준 9012 괄호 c++ [컴공과고씨]
시간빌게이츠
2022. 4. 16. 14:17
반응형
https://www.acmicpc.net/problem/9012
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
이 문제를 보고 처음에는 당연히 queue를 떠올리기 어려울 수 있지만 한 번 직접 괄호 지우다 보면 queue가 떠올라야한다.

이런식으로 앞에 나온 ( 가 있다면 ) 나왔을 때 (을 지워주는 형식으로 할 것이다. 그런데 만약 남아있는 ( 있거나 ( 가 나오지 않았는데 ) 나온다면 그것도 잘못된 괄호이다. 그래서 큐를 이용하는 것이다.
먼저 ( 일 경우 큐에 push 해주고 만약 ) 나왔다면 큐에서 pop해주면 된다.
이때 큐가 비어있는데 pop을 하려고 하면 no를 출력 만약 마지막 까지 연산이 끝났는데 큐가 비어있지 않으면 ( 남아있다는 것이니 이것도 no를 출력해주면 된다.
단계별 풀이
1. 입력 된 값을 하나씩 보면서 ( 가 나오면 큐에 push 해준다.
2. 만약 ) 나왔다면 먼저 큐가 비어있는지 확인해서 비어있다면 no를 출력해준다.
3. 만약 비어있지 않다면 큐를 pop해준다.
4. 연산이 끝난 후 큐가 비어있다면 yes를 비어있지 않다면 no를 출력해준다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main(){
int n;
string s;
cin >> n;
for (int i = 0; i < n; i++){
queue<char> q;
cin >> s;
bool flag = true;
for (int i = 0; i < s.length();i++){
if (s[i] == '('){
q.push(s[i]);
}
else{
if (q.empty()){ // ( 가 없는데 ) 나옴
cout << "NO" << '\n';
flag = false;
break;
}
q.pop();
}
}
if(flag){
if(q.empty()){
cout << "YES"<< '\n';
}else{ // ( 가 남아있음
cout << "NO"<< '\n';
}
}
}
return 0;
} //16min
|
cs |
체감 난이도 | 걸린시간 | 참고 | 사용 문법 |
하 | 16min | x | queue |
반응형