<알고리즘 문제풀이&연습>/[C++] 백준

[백준 9012] 괄호 (stack)

사용자 BlockDMask 2017. 9. 20. 16:48
반응형
  • 안녕하세요. BlockDMask 입니다.

  • 백준 알고리즘 사이트에서 단계별로 풀어보기를 하나하나 하고있습니다. ㅎㅎ

0. 제목

  • 백준 9012 괄호

  • BOJ 9012 괄호

1. 문제설명


괄호 문자열 (Parenthesis String, PS)는 '(', ')' 만으로 구성되어 있는 문자열을 말합니다.

흔히 우리가 말하는 소괄호.!


그 중 괄호의 모양이 바르게 구성된 올바른 괄호 문자열을 Valid PS, VPS라고 부릅니다.


"()" 는 VPS 입니다.

"()()(())" 는 VPS 입니다.

"())" 는 VPS 가 아닙니다.


처음 Test할 문자열의 갯수 N이 들어오고 

그다음 문자열이 N개 만큼 들어옵니다.


입력된 괄호 문자열이 올바른 괄호 문자열(VPS)이면 "YES"를 아니면 "NO"를 한줄에 하나씩 출력하시오.


2. 풀이과정


C++ STL 에서 지원해주는 stack 을 사용했습니다.


stack 을 사용하여 받은 문자열에서


[여는 괄호 일때] 

push


[닫는 괄호 일때]


1) 스택 내부에 여는 괄호가 있다. -> pop

2) 없다 -> false


[문자열을 다 확인했는데]

스택 내부에 여는 괄호가 있다 -> false


로 알고리즘을 구현했습니다.


3. 코드


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
38
39
40
41
42
43
44
45
46
47
//백준 9012번 괄호
 
#include<iostream>
#include<stack>
#include<string>
 
using namespace std;
 
bool Check(string str){
    int len = (int)str.length(); //문자열 길이
    stack<char> st;              //char 타입을 받는 stack 선언
 
    for(int i=0; i<len ; i++) { //문자열 길이만큼 반복문
        char c = str[i];        //문자 하나씩 받음
 
        if(c == '('){
            st.push(str[i]);    //여는 괄호면 push
        }else{
            if(!st.empty()){    //닫는 괄호면 stack 이 비어있는지 확인후
                st.pop();       //스택이 비어있지 않으면 pop
            }else{
                return false;   //비어있으면 false.
            }
        }
    }
 
    return st.empty();          //반복문이 끝나고 스택에 괄호가 남아있으면 false
}
 
int main(void){
 
    int n;
    cin >> n;
 
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
 
        if(Check(str)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
 
    return 0;
}
cs


4. 인증


문제출처 - https://www.acmicpc.net/problem/9012

감사합니다. 한번 꾹 부탁드립니다.!

반응형

'<알고리즘 문제풀이&연습> > [C++] 백준' 카테고리의 다른 글

[백준 13458] 시험 감독  (1) 2017.09.26
[백준 2292] 벌집  (1) 2017.09.26
[백준 1427] 소트인사이드  (2) 2017.09.23
[백준 1316] 그룹 단어 체커  (4) 2017.09.21
[백준 9012] 괄호 (stack)  (0) 2017.09.20
[백준 1016] 제곱ㄴㄴ수  (0) 2017.09.19
[백준 11005] 진법 변환 2  (0) 2017.09.19
[백준 2908] 상수  (4) 2017.09.17
[백준 2675] 문자열 반복  (0) 2017.09.17