[백준] 키로거 (C++)

문제

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

입력된 문자열을 토대로 비밀번호를 출력하는 문제이다.

 

입력에는 3가지의 규칙이 존재한다.

• ' < ' 은 커서 왼쪽 이동
• ' > ' 은 커서 오른쪽 이동
• ' - ' 은 커서 바로 앞 문자 지우기

---

풀이

vector를 이용하여 해당 문제를 풀이했지만 시간 초과가 났다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int cursor = 0;

void GetPassword(string input) {
	int length = input.length(), cursor = 0, n= 0;
	vector<char> password;

	for (int i = 0; i < length; i++) {
		char c = input[i];

		if (c == '<') {
			cursor = max(cursor - 1, 0);
		}
		else if (c == '>') {
			int l = password.size();
			cursor = min(cursor + 1, l);
		}
		else if (c == '-') {
			if (cursor > 0) {
				password.erase(password.begin() + cursor - 1);
				cursor = max(cursor - 1, 0);
			}
		}
		else {
			password.insert(password.begin() + cursor, c);
			int l = password.size();
			cursor = min(cursor + 1, l);
		}
	}

	for (int i = 0; i < password.size(); i++) {
		cout << password[i];
	}
	cout << '\n';
}

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

	cin >> n;

	vector<string> vec(n);

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		GetPassword(input);
	}


	return 0;
}

그래서 연결 리스트인 List를 이용하여 해당 문제를 풀이했다.

List는 커서의 위치만 정해져 있다면 삽입과 삭제 연산을 O(1) 시간 복잡도로 수행할 수 있어, 이 문제를 해결하는 데 적합한 자료구조였다.

#include <iostream>
#include <string>
#include <list>

using namespace std;

void GetPassword(string input) {
	list<char> password;
	auto cursor = password.begin();

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

		if (c == '<') {
			if (cursor != password.begin())
				cursor--;
		}
		else if (c == '>') {
			if (cursor != password.end())
				cursor++;
		}
		else if (c == '-') {
			if (cursor != password.begin()) {
				cursor--;
				cursor = password.erase(cursor);
			}
		}
		else {
			password.insert(cursor, c);
		}
	}

	for (auto iter = password.begin();iter != password.end(); iter++) {
		cout << *iter;
	}
	cout << '\n';
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		GetPassword(input);
	}

	return 0;
}