[백준]25497번: 기술 연계마스터 임스

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

25497번: 기술 연계마스터 임스

자료구조 알고리즘 중 stack을 이용한 문제다.

푼 사람이 적어 내가 고민한 아이디어를 공유해보려 한다.

 

string을 통해 기술을 입력 받는다면 사실상 N은 필요없다.

접근 아이디어는 다음과 같다.

스킬을 보면 SK와 LR은 세트다.

즉 S가 먼저 나와야 K가 가능하고 L이 먼저 나와야 R이 가능하다.

그렇다면 이 두개의 세트를 담을 stack을 준비한다.

각 stack은 SK와 LR만을 담는다. 이때 lrCombo stack은 LR만을 skCombo stack은 SK 기술만을 처리한다.

 

1) S와 L이면 무조건 해당 기술 stack에 넣는다.

2) K와 R은 각 기술 stack이 비어있는지 확인한다.

2-1) 각 기술 stack이 비어있다면 그냥 넘긴다.

2-2) 각 기술 stack에 선 기술이 있다면 사용으로 처리한다.

3) 그 외 모든 숫자는 항상 기술 사용으로 처리한다.

여기서 기술 사용으로 처리한다 부분이 문제에서 원하는 기술이 정상적으로 발동되는 횟수다.

#include<iostream>
#include<stack>

#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

int main(void)
{
	FastIO;
	
	int N = 0; // 총 기술 사용 횟수 N
	cin >> N;
	string skill;
	cin >> skill;

	stack<char> lrCombo;
	stack<char> skCombo;
	int skillUseCnt = 0;
	for ( int i = 0; i < skill.size(); i++ )
	{
		if ( skill[i] == 'L' )
		{
			lrCombo.push(skill[i]);
		}
		else if ( skill[i] == 'S' )
		{
			skCombo.push(skill[i]);
		}
		else if ( skill[i] == 'K' )
		{
			if ( !skCombo.empty() )
			{
				skillUseCnt++;
				skCombo.pop();
			}
			else
				break;
		}
		else if ( skill[i] == 'R' )
		{
			if ( !lrCombo.empty() )
			{
				skillUseCnt++;
				lrCombo.pop();
			}
			else
			{
				break;
			}
		}
		else
		{
			skillUseCnt++;
		}	
	}

	cout << skillUseCnt << "\n";
	return 0;
}