백준 - 괄호 9012

 

 

괄호를 풀기 전에

스택이라는 개념을 잡고 풀어보자.

 

 

 Stack은 '쌓다', 또는 '무언가가 쌓여 있는 더미'등을 의미한다.

스택은 의미 그대로 어떤 데이터를 삽입/삭제하는 과정을 '쌓는' 형태로 나타낼 수 있는 자료구조이다.

 

 

출저 위키백과

 

 

 스택은 FILO 구조로 처음에 넣은 데이터는 가장 아래에 위치하게 된다.

다음 들어오는 데이터들은 그 위에 순서대로 쌓인다.

데이터들을 뺄 때는 제일 위에 있는 데이터부터 빼야 한다.

결과적으로 가장 처음에 넣은 데이터는 가장 마지막에 빠지게 된다.

이를 First-In-Last-Out이라고 한다.

반대로 가장 마지막에 들어왔던 데이터는 가장 먼저 빠진다

이를 Last-In-First-Out 이라고 한다.

이것이 스택의 특징이다.

 

스택에 대한 예로는

인터넷 웹 서핑을 할 때 접속한 페이지 기록이 스택 구조로 관리되는 것을 예를 들 수 있다.

 

웹 페이지를 뒤로 가기/앞으로 가기를 구현 한다면 스택 2개를 사용하여

서로 반대 방향의 스택을 넣어주면 된다.

 

뒤로 가기를 누르면 방금 전에 방문했던 화면으로 돌아간다.

방문한 페이지가 순서대로 스택에 삽입/삭제 되는 것이다.

 

스택에 데이터를 넣고 뺄 때 시간 복잡도는 O(1)이므로

만약 N개의 데이터를 넣오 뺴야 한다면 총 O(N)이 될 것이다.

 

 스택은 DFS 등 다른 알고리즘에서 사용되는 자료구조이기도 하며,

스택 자체를 활용하는 문제들도 자주 출제가 된다.

스택 활용 문제에서는 입력을 순차적으로 살펴보면서 각각의 데이터를

스택에 언제 넣고 뺄지 결정하는 게 핵심 포인트가 될 때가 많다.

 

스택을 사용하지 않고 푼다면 시간 초과가 발생하게 N을 크게 둬서

결국을 스택을 사용해만 풀리도록 하는 문제들도 많다.

스택은 C++에서 STL로 제공한다.

 

 

#include <string>
#include <iostream>
#include <stack>

using namespace std;


int main()
{
    
    int num;

    cin >> num; 

    while (num-- != 0)
    {
       
        string x = "";
        string answer = "YES";
    
        stack<char> s;
        cin >> x;   
        for (unsigned int i = 0; i < x.length(); i++)
        {
            if (x[i] == '(')
            {
                s.push(x[i]);
            }
    
            else
            {
                if (!s.empty())
                {
                    s.pop();
                }
                else
                {
                    answer = "NO";
                    break;
                }
            }

        }
        if (!s.empty())
        {
            answer = "NO";
        }

        cout << answer << endl;
    }
    
    

    return 0;
}