[기본] 스택 자료구조 활용

 

스택을 활용해야하는 문제

스택을 활용해야 하는 경우는 보통 짝을 짓는 문제입니다. 남녀가 반복돼서 나타나거나, 동물 등등 교차로 반복되는 상황에서 짝을 맞춰야하는 경우에 사용합니다. 그 중 대표적인 문제는 괄호입니다. 괄호는 반드시 여는 괄호와 닫는 괄호가 짝이 이루어져야겠죠. 그렇지 않으면, 문제가 발생합니다. json파일을 분석할 때도 괄호의 여닫음을 분석해야 합니다. 중첩으로 객체가 있을 수 있고 그 내부에 array까지 있다면, 함수 콜 스택 처럼 내부로 들어갔다가 나올때 닫는 괄호를 기준으로 빠져나오게 됩니다.

 

stack의 동작

 

 

문제 풀기

백준 9012: 괄호(링크)

 

풀이

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

int main() 
{
    int count;
    cin >> count;

    for (int i = 0; i < count; i++)
    {
        string str;
        cin >> str;

        stack<int> s;
        bool error = false;
        for (int j = 0; j < str.size(); j++)
        {
            if (str[j] == '(')
                s.push(str[j]);
            else
            {
                if (s.empty())
                {
                    error = true;
                    printf("NO\n");
                    break;
                }

                s.pop();
            }
        }

        if (!error)
            printf("%s\n", s.empty() ? "YES" : "NO");
    }
}

 

여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택에서 뺍니다. 닫는 괄호 차례에서 스택이 비어있으면 닫는 괄호가 더 많아서, 문제가 있는 경우입니다. 반대로 모든 문자열을 순회했는데 스택이 비어있지 않다면 여는 괄호가 더 많은 경우입니다.

 

스택을 쓰지 않는 풀이

#include <iostream>
#include <stack>
int main()
{
	int T;
	std::cin >> T;
	std::string PS;

	int count;
	for (int i = 0; i < T; i++)
	{
		std::cin >> PS;
		count = 0;
		
		for (int j = 0; j < PS.size(); j++)
		{
			if (PS[j] == '(')
				count++;
			else
				count--;

			if (count < 0)
				break;
		}

		if (count == 0)
			std::cout << "YES\n";
		else
			std::cout << "NO\n";
	}
}

물론 스택을 쓰지 않고, count를 활용할 수도 있습니다. 괄호문제처럼 직관적인 문제는 다른 방법으로 충분히 풀지만, DFS와 같은 문제가 나오면 스택의 활용도가 더 올라갑니다.