백준 온라인 저지 | 5397번 키로거 | C++

백준 온라인 저지 | 5397번 키로거 | C++

5397번: 키로거

 

1. 문제 정의

■ 1.1 리스트 반복자

 강산이가 비밀번호 창에서 입력한 키가 주어지고 이 키는 알파벳 대문자, 알파벳 소문자, 숫자, 백스페이스, 화살표 키로 구성된다. 강산이가 입력한 길이가 L인 문자열에서 화살표 키로 커서를 움직이거나 백스페이스 키로 문자를 지워야 하기 때문에 데이터를 중간에 삽입하고 삭제하기 편한 리스트(list)로 코드를 구현하는 것이 적절해 보인다.

 

■ 1.2 리스트 메서드

 리스트로 키로거를 구현하기 전, 강산이가 입력한 키의 기능을 구현하는 데 사용할 몇 가지 메서드를 미리 알아본다. 첫 번째, 알파벳 대문자와 소문자는 리스트에 삽입할 문자이므로 insert 메서드를 사용한다. 반대로 백스페이스는 리스트에서 문자를 삭제하므로 erase 메서드를 사용한다. 커서를 움직이는 화살표 키는 반복자에 operator++, operator--를 적용하여 구현할 수 있다.

 

2. 문제 풀이

■ 2.1 풀이 가이드

1. 강산이가 입력한 문자열 L로 벡터 v를 초기화하고 이 문자열에서 순수한 비밀번호만 저장할 리스트 l을 선언한다.
2. 커서 역할을 하는 반복자 cursor를 begin 메서드로 리스트의 첫 번째 원소를 가리키게 한다.
3. for문으로 벡터에 저장된 문자를 모두 조사할 때까지 다음 과정을 반복한다.
   • 오른쪽 화살표(>)는 operator++로 cursor가 다음 원소를 가리키게 한다.
   • 왼쪽 화살표(<)는 operator--로 cursor가 이전 원소를 가리키게 한다.
   • 백스페이스(-)는 operator--로 cursor가 이전 원소를 가리키게 하고 erase 메서드로 문자를 삭제한다. 이때 erase 메서드에서 반환된 값을 cursor에 대입하여 다음 원소를 가리키게 한다.
   • 알파벳 대소문자는 insert 메서드로 cursor가 가리키는 위치에 문자를 삽입한다.
4. 순수한 비밀번호만 저장된 리스트 l을 출력한다.

 

■ 2.2 시간 복잡도

 리스트를 통해 구현한 키로거는 문자를 삽입하거나 삭제하는 데 O(1)의 시간 복잡도를 가진다.

 

3. 문제 해결

#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		// 강산이가 입력한 키를 문자열로 받습니다.
		string L;
		cin >> L;

		list<char> l;
		// 문자열 L로 벡터를 초기화합니다.
		vector<char> v(L.begin(), L.end());
		// 커서(반복자)의 위치를 리스트 begin으로 설정합니다.
		auto cursor = l.begin();
		
		for (auto vIter = v.begin(); vIter != v.end(); ++vIter) {
			switch (*vIter) {
			// < 화살표는 커서를 왼쪽으로 한 칸 옮깁니다.
			case '<':
				if (cursor != l.begin()) {
					cursor--;
				}
				break;
			// > 화살표는 커서를 오른쪽으로 한 칸 옮깁니다.
			case '>':
				if (cursor != l.end()) {
					cursor++;
				}
				break;
			// 백스페이스는 커서 왼쪽의 문자를 삭제합니다.
			case '-':
				if (cursor != l.begin()) {
					cursor--;
					cursor = l.erase(cursor);
				}
				break;
			// 알파벳은 커서 왼쪽에 문자를 삽입합니다.
			default:
				l.insert(cursor, *vIter);
				break;
			}
		}

		// 리스트에 저장된 순수한 비밀번호를 출력합니다.
		for (const auto& e : l) {
			cout << e;
		}
		cout << '\n';
	}
	return 0;
}

 

그림 5397번 키로거 성공

 

4. 문제 고찰

■ 4.1 벡터 생성자

 강산이가 입력한 문자열 L에서 벡터 v를 초기화할 때 반복자를 사용할 수 있다. 다음과 같이 begin 메서드와 end 메서드를 생성자에 첫 번째, 두 번째 인수로 전달하면 for문을 사용하지 않고 벡터를 초기화할 수 있다.

// 벡터 v의 생성자에 문자열 L의 반복자를 전달하여 초기화합니다.
vector<char> v(L.begin(), L.end());

 

■ 4.2 느낀 점

 1406번 에디터와 100% 같은 문제여서 상당히 쉬웠다. erase 메서드가 다음 원소에 대한 포인터를 반환하기 때문에 반복자 cursor를 계속해서 사용하려면 이 반환 값을 대입해주어야 한다는 것을 잊지 않고 있었다. 덕분에 별 탈 없이 문제를 해결할 수 있었다.