[백준] 5397번: 키로거

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

5397번: 키로거

list로 푸는게 속도가 더 빠를 것이라고 생각했는데 deque으로 푸는게 더 빨랐다.

deque이 list보다 메모리를 덜 잡아먹어서 그런가..?

(vector로 풀면 시간초과가 뜬다)

 

아무튼 풀이방법은 password를 한글자씩 저장하는 deque을 선언한 뒤,

현재 커서의 위치를 cursor라는 포인터에 저장한다.

 

그리고 나서 입력 문자열을 한 글자씩 탐색하면서

< : cursor 감소

> : cursor 증가

- : cursor 바로 앞 요소 삭제

그 외: cursor 위치에 요소 삽입 후 cursor 증가

하면 된다.

 

간단한 구현인데 자꾸 에러가 떠서 왜 그런가 했더니, insert, erase를 하면 iteratar의 위치가 달라지기 때문이었다.

password.erase(--cursor); 이렇게 쓰지 말고 cursor = password.erase(--cursor); 이렇게 써줘야 한다.

(이것도 자료구조별로 달라진다.)

 

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

void keyLogger() {
	string input;
	deque<char> password;
	deque<char>::iterator cursor = password.end();

	cin >> input;

	for (int i = 0; i < input.length(); i++) {
		switch (input[i]) {
		case '<':
			if (cursor != password.begin()) cursor--;
			break;
		case '>':
			if (cursor != password.end()) cursor++;
			break;
		case '-':
			if (cursor != password.begin()) {
				cursor = password.erase(--cursor);
			}
			break;
		default:
			cursor = password.insert(cursor, input[i]);
			cursor++;
		}
	}

	for (cursor = password.begin(); cursor != password.end(); cursor++) {
		cout << *cursor;
	}
	cout << "\n";
	password.clear();
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		keyLogger();
	}
}