(백준BAEKJOOB )- 9012번 -괄호 "c++"

 

일단 이문제가 왜 스택을 이용하는지 생각 해보았는데 

스택에 '(' 한개만을 이용하면

쉽게 문제를 풀수 있다는 것을 알게 되었다.

코드 1번

 

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

int main(void) {
	int k;
	cin >> k;

	while (k--) {
		string input;
		cin >> input;

		stack<char> stack;
		string a = "YES";
		for (int i = 0; i < input.length(); i++) {
			if (input[i] == '(') {
				stack.push(input[i]);
			}
			else if (!stack.empty() && input[i] == ')' && stack.top() == '(') {
				stack.pop();
			}
			else{a = "NO"; break;}
		}
		if (!stack.empty()) {a = "NO";}

		cout << a << endl;
	}
	return 0;
}

메모리 2024KB사용 

input 에 '(' 를 넣어주고

 

만약에 스택에 비었거나 ')' 괄호거나

스택 top에 '(' 가있으면 pop시켜준다!

 

사실상

( 

괄호 한개를 스택에 저장시키고 

) 이괄호가 들어오게된다면

( 이괄호를 pop시켜주는 구조이다.

 

 

 

 

코드 2번
참고 자료 <https://hagisilecoding.tistory.com/75>

#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

이걸 큐로 풀수 있다는 것을 생각하지 못했다..

스택만 생각나긴했다 이코드 또한 

메모리는 2024kb를 이용하였다.

 

/ 큐 코드 주석 달기 /