백준 9012번 C / C++ 풀이

https://www.acmicpc.net/problem/9012

9012번: 괄호

알고보니 스택을 이용해서 풀어야 했던 문제. 자료구조를 배우고 나면 다시 풀어봐야겠다.

 

#include <stdio.h>
#include <string.h>

int main() {
	int ntest;
	char buf[100];
	int i;
	int count1, count2;
    int len;
	scanf("%d", &ntest);
	while (ntest--) {
		scanf("%s", buf); // 1라인 입력
		count1 = count2 = 0;
        len = strlen(buf);
		// 문자열을 모두 검사해서
        if (buf[0] == ')' || buf[len - 1] == '(')
            printf("NO\n");
        else {
            for (i = 0; i < len; i++) {
                // ( 갯수와 ) 갯수를 count하고
                buf[i] == '(' ? count1++ : count2++;
                if (count1 - count2 == -1) break;
            }
    		// count1 count2 를 비교하여 판단
            if (count1 == count2) printf("YES\n");
            else printf("NO\n");
        }
	}
}

 

---

22.01.16

스택을 어느정도 공부하고 나니 이 문제를 스택으로 다시풀겠다고 다짐했었기 때문에, 이 문제를 스택으로 다시 풀고 싶어졌다. 

 

방법은 생각보다 간단하다. 괄호가 들어올 때, "("가 들어오면 스택에 push하고 ")"이 들어올 때 스택이 비어있다면 vps가 아니기 때문에 false, 비어있지 않다면 스택에서 pop하면 된다.

 

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool is_vps(string& str) {
    if (str[0] == ')' || str[str.length() - 1] == '(')
        return false;
    
    else {
        stack<char> st;
        
        for(const auto& x : str) {
            if(x == '(') st.push(x);
            else {
                if (st.empty()) return false;
                else st.pop();
            }
        }
        return st.empty();
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    bool flag;
    string str;
    stack<char> st;

    cin >> t;
    
    while(t--) {
        cin >> str;
        if(is_vps(str)) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

C99 : 첫번째 풀이 / C++17: 두번째 풀이