C++ [키로거_백준] / #stack #자료구조

Problem

---

키로거_백준

5397번: 키로거

하나의 문자열이 주어진다.

해당 문자열에는 문자들의 정보, backspace, 커서 이동에 대한 정보가 주어진다.

결과로 완성된 문자열을 출력하는 문제이다.

 

Solve

---

배열이나 vector를 이용해서 커서의 위치를 바꿔가며 문자를 추가하거나 제거할 생각이었다.

그러나 풀어도 마땅한 풀이가 떠오르지않아 문제하단의 알고리즘 분류를 클릭하여 힌트를 얻었다.

stack을 보고 뒤통수를 맞은 기분이었다. stack으로 풀면 정말 쉽게 구현할 수 있다.

두개의 stack 객체가 필요하다.

a : 커서 왼쪽에 있는 문자들을 저장한다.

b : 커서 오른쪽에 있는 문자들을 저장한다.

 

1.  키로거 문자열 L의 문자들을 하나씩 확인한다.

2. >이면 커서 한칸 오른쪽으로 이동 -> b의 top을 a의 top으로 이동

    // 커서 위치가 이미 가장 오른쪽에 위치하면 break; (b가 empty인 경우)

 

3. < 이면 커서 한칸 왼쪽으로 이동 -> a의 top을 b의 top으로 이동

    // 커서 위치가 이미 가장 왼쪽에 위치하면 break; (a가 empty인 경우)

4. -이면 커서 위치의 문자 제거 -> a의 top 제거

5. 나머지 문자는 커서의 위치에 추가 -> a.push로 추가

6. 위의 과정을 거치면 stack 구조이기 때문에 a에는 반대로 문자가 담겨있다.

따라서 a의 문자를 b에 옮긴뒤 b를 전부 출력.

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T;
	cin >> T;
	stack<char> a;
	stack<char> b;

	string L;
	for (int j = 0; j < T; j++)
	{
		cin >> L;
		for (int i = 0; i < L.length(); i++)
		{
			switch (L[i])
			{
			case '<':
				if (!a.empty())
				{
					b.push(a.top());
					a.pop();
				}
				break;
			case '>':
				if (!b.empty())
				{
					a.push(b.top());
					b.pop();
				}
				break;
			case '-':
				if (!a.empty())
				{
					a.pop();
				}
				break;
			default:
				a.push(L[i]);
				break;
			}
		}
		int as = a.size();
		for (int i = 0; i < as; i++)
		{
			b.push(a.top());
			a.pop();
		}
		int si = b.size();
		for (int i = 0; i < si; i++)
		{
			cout << b.top();
			b.pop();
		}
		cout << '\n';
	}
	return 0;
}