관심이 가는 개발 보물창고

풀이

스택에 문자열을 하나씩 집어넣으면서 괄호 쌍("{}")이 맞다면 스택을 비워주고,

아니라면 계속해서 스택에 넣어준다.

모든 문자열을 다 순환했을 때,

스택이 비어있다면 주어진 문자열은 모두 안정적인 문자열이다.

스택이 비어있지 않다면 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 연산을 해야 한다.

몇 번 손으로 쓰다 보면 규칙을 찾을 수 있다.

{ { 나 } } 는 1번 만에 안정적인 문자열을 만들 수 있지만

} { 는 2번 연산을 적용해야 안정적인 문자열을 만들 수 있다.

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

int main()
{
	string s;
	int n = 0;
	int cnt = 0;
	while (getline(cin, s))
	{
		if (s[0] == '-')
			break;

		n++;
		cnt = 0;
		stack<char> st;
		for (int i = 0; i < s.length(); i++)
		{
			if (!st.empty() && st.top() == '{' && s[i] == '}')
				st.pop();
			else
				st.push(s[i]);
		}

		while (!st.empty())
		{
			char c1 = st.top(); st.pop();
			char c2 = st.top(); st.pop();

			if (c1 == c2)
				cnt++;
			else
				cnt += 2;
		}

		cout << n << ". " << cnt << '\n';
	}
	return 0;
}

풀이

stack 자료구조를 사용하면 쉽게 해결할 수 있다.

줄이 1 ~ 6이므로 stack을 배열처럼 사용하면 여러 개의 stack 줄이 생기게 된다.

현재 top과 치려고 하는 프렛의 번호를 비교해서 count를 매기면 된다.

치려고 하는 프렛의 번호를 b라고 하면

top() > b 이면,

pop 해주고 count++

top() == b이면,

굳이 손을 다른 프렛으로 옮기지 않아도 되므로 패스

top() < b이면,

push 하고 count++

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

int n, p;
stack<int> st[7];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> p;

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;

		while (1)
		{
			if (st[a].empty())
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() < b)
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() == b)
				break;
			else if (!st[a].empty() && st[a].top() > b)
			{
				st[a].pop();
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}