[Baekjoon, C++] 9012번 : 괄호

백준 단계별 풀기에서 스택 3번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/9012

9012번: 괄호

---

백준 9012번 괄호 : 문제, 입력, 출력

---

이 문제에서는 규칙을 찾는 것이 꾀나 중요할 것이다. 

 

 처음으로 생각 했던 것은, '('의 개수와 ')' 개수가 같으면 VPS일 것이다 라고 생각했다. 하지만 ( ) ) ( ( ) 의 경우를 보자. 개수는 3개, 3개로 같으나, 가운데의 ')' 와 '('는 짝을 이루지 못한다. 따라서, 개수가 같은 것이 VPS를 모두 포함할 수 없다. 

 

 다음으로는, 스택과 연관지어 생각해보자. VPS가 결국에는 '('와 ')'의 짝이 맞아야 한다고 볼 수 있을 것이다. 그렇다면, '(' 일 때는 스택에 '('를 push, ')'일 때는 '('를 pop을 한 뒤 나중에 스택에 아무것도 남아 있지 않다면 VPS로 볼 수 있을까? 가능할 것 같다. 하지만, 지금 고려한 부분 이외에 추가적으로 고민 해야할 것이 2개 있다.

 

 1. ')'일 때 pop을 하지만, 스택이 비어있다면? pop 할 수 없다. empty인 경우를 만들면 않되니까 push 한다.

 2. ')'일 때 스택의 상단이 '('가 아니라면? 1번에 스택이 비어있을 경우를 처리한다면, ')' 일때를 의미할 것이다. 스택이 empty인 경우만 만들지 않으면 된다. 아무처리도 하지 않거나, push 한다. 

 

 따라서, pop하는 경우가 상당히 제한적이다. 스택이 비어있지 않고, ')'일때이며, 스택의 상단이 '('이어야 한다. 그렇다면 case를 push하는 경우와 pop하는 경우로 나눠보자. push 하는 경우는, 스택이 비어있을때와 '('일 경우이다. pop을 하는 경우는 스택이 비어있을때도 아니고, '('일 경우도 아니고, 스택의 상단이 '('일 경우이다.

if(스택이 비었을 경우 or '('일 경우) {
	push;
}else if(스택의 상단이 '('일 경우) {
	pop;
} 

---

for문을 통해 사용자에게 받을 값은 문자열이다. ex. ( ( ) ( ) ) 

따라서, string 라이브러리를 사용한다.

---

Visual Studio 2019로 코드를 작성한 결과다. 간단한 설명을 라인마다 주석을 달아 놓았다.

 

#include<iostream>
#include<stack>    // 표준 라이브러리 stack을 사용하기 위함
#include<string>
 
using namespace std;
 
int main() {
    int numberOfVPS; // VPS 문자열 개수 K 선언
 
    cin >> numberOfVPS;  //K 값을 받는다. 
 
    for (int i = 0; i < numberOfVPS; i++) {
        string vps;       // 유저로 부터 문자열을 받을 변수 선언.
        stack<char> st;
 
        cin >> vps;       // 문자열(VPS)을 받는다. 
 
        for (int j = 0; j < vps.length(); j++) {
            if (st.empty() || vps[j] == '(') { //스택이 비었을때와 문자값이 '('일때
                st.push(vps[j]);
            }
            else if (st.top() == '(') {       //스택이 비어있지 않고, 문자값이 ')'일때, 스택의 상단이 '('라면
                st.pop();
            }
        }
 
        if (st.empty()) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
 
    }
    return 0;
}
 

 

이상으로 9012번 문제 괄호 였다. 피드백은 언제나 환영이다.