백준 5397 - 키로거

문제 설명

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 문자열을 보고 규칙에 맞게 파싱하여 결과 문자열을 출력하면 된다.

 

규칙은 다음과 같다.

• "<": 커서를 왼쪽으로 이동
• ">": 커서를 오른쪽으로 이동
• "-": 커서에 위치한 문자 지우기

 

주어진 문자열을 규칙에 따라 처리한다면 시간 초과가 발생할 수 있다.

string에 대한 연산은 비싸기 때문이다.

따라서, 다른 방법으로 처리할 필요가 있다.

 

규칙을 보면 커서 이동과 커서 위치의 문자를 지우는 연산이 있다.

이는 모두 커서를 중심을 이루어진다는 것을 알 수 있다.

즉, 커서의 위치를 계속하여 관리해야 하는데 이를 두개의 deque로 나눈다면 간단하게 해결할 수 있다.

커서 앞에 있는 deque와 커서 뒤에 있는 deque를 관리한다면 커서 이동시 방향에 따라 다른 쪽으로 보내면 된다.

문자를 지우는 연산은 커서 앞에 있는 deque의 back을 지우면 간단하다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;

void Parse(string input)
{
	deque<char> front;
	deque<char> rear;

	for (int i = 0; i < input.length(); i++)
	{
		auto letter = input[i];

		if (letter == '<')
		{
			if (front.empty()) continue;
			auto c = front.back();
			front.pop_back();
			rear.push_front(c);
		}
		else if (letter == '>')
		{
			if (rear.empty()) continue;
			auto c = rear.front();
			rear.pop_front();
			front.push_back(c);
		}
		else if (letter == '-')
		{
			if (front.empty()) continue;
			front.pop_back();
		}
		else
		{
			front.push_back(letter);
		}
	}

	for (auto c : front)
	{
		cout << c;
	}
	for (auto c : rear)
	{
		cout << c;
	}

	cout << "\n";
}

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

	cin >> N;

	while (N--)
	{
		string pwd;
		cin >> pwd;

		Parse(pwd);
	}

	return 0;
}

---