[실5] 25497 - 기술 연계마스터 임스

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

int main() 
{
	int n, cnt = 0;
	stack<char> lr, sk;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		char c;
		cin >> c;
		
		if (isdigit(c))
			cnt++;

		else
		{
			if (c == 'L')
				lr.push(c);

			else if (c == 'S')
				sk.push(c);

			else if (c == 'R')
			{
				if (!lr.empty())
				{
					lr.pop();
					cnt++;
				}
				else
					break;
			}
			else
			{
				if (!sk.empty())
				{
					sk.pop();
					cnt++;
				}
				else
					break;
			}
		}
	}
	cout << cnt;
}

 

본인 코드 (시간 초과)

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

using ll = long long;
using iter = std::list<char>::iterator;

list<char> lc;
 
int cnt;

bool IsMatching(char l, char r)
{
	if ((l == 'L' && r == 'R') ||
		(l == 'R' && r == 'L'))
		return true;

	if ((l == 'S' && r == 'K') ||
		(l == 'K' && r == 'S'))
		return true;

	return false;
}

bool Check(iter left, iter right)
{
	if (right == lc.end())
		return false;

	auto l = *left, r = *right;

	if (IsMatching(l, r))
	{
		lc.erase(left);
		lc.erase(right);
		cnt++;
		return true;
	}
	return false;
}

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

	for (int i = 0; i < n; i++)
	{
		char c;
		cin >> c;
		
		if (isdigit(c))
			cnt++;

		else
			lc.push_back(c);
	}
	if (lc.size() > 1)
	{
		auto begin = lc.begin();
		auto end = ++lc.begin();

		while (begin != end)
		{
			if (Check(begin, end))
			{
				begin = lc.begin();

				if (begin == lc.end())
					break;

				end = ++lc.begin();
			}
			else
			{
				begin++;

				if (begin == lc.end())
					break;

				end++;
			}
		}
	}
	cout << cnt;
}