[스택] 9012. 괄호

1. 문제 해결 전략

처음에 조건을 떠올렸을 때 두 가지를 떠올렸다. 

'(' 와 ')'는 개수가 같아야 하며, 각각을 벡터에 문자 순서대로 집어넣었을 때, 무조건 '('의 순번이 ')'의 순번보다

빨라야 한다는 것.  왜냐하면 ')'는 앞에 무조건 '('가 있어야 하는데 서로를 다른 집합에 순서대로 분리해뒀다면 ')'가 '('보다 빠른 순번을 가져야하기 때문이다.

 

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

vector<string> str;

void printfunc(string s)
{
	vector<int> left;
	vector<int> right;
	int i = 0;
	for (auto it = s.begin(); it != s.end(); ++it)
	{
		if ((*it) == (char)('('))
		{
			left.push_back(i++);
		}
		else if ((*it) == char(')'))
		{
			right.push_back(i++);
		}
	}

	if (left.size() != right.size())
	{
		std::cout << "NO" << std::endl;
		return;
	}

	for (auto it = s.begin(); it != s.end(); ++it)
	{
		if (left.empty() || right.empty())
			break;

		if (left.back() > right.back())
		{
			std::cout << "NO" << std::endl;
			return;
		}
		else
		{
			left.pop_back();
			right.pop_back();
		}
	}

	std::cout << "YES" << std::endl;
}

int main()
{
	int n;
	std::cin >> n;

	for (int i = 0; i < n; i++)
	{
		char pdata[256];
		cin >> pdata;
		string st;
		st = pdata;
		str.push_back(st);
	}

	for (auto iter = str.begin(); iter != str.end(); ++iter)
	{
		printfunc(*iter);
	}
}

문제유형이 stack인데 아마도 내 접근방법과는 역으로 ')'부터 접근하면서 짝 counting을 하는 것같다. 확실히 내 코드는 메모리를 더 많이 사용하는 느낌이 있지만 통과했으니 상관은 없다 ㅎㅎ.

 

2. 걸린 시간

10분

 

3. 느낀점

처음 생각대로 바로바로 코드가 짜여졌으면 더 빨리 풀수있었는데 어이없게 조건문에서 '=='가 아니라 '='를 쓰고

왜 안되는지 헤매는 바보같은 짓을 했다 ㅋㅋㅋ 빡치는 문제..

 

4. 링크

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