Deff_Dev
[백준] 키로거 (C++) 본문
문제
입력된 문자열을 토대로 비밀번호를 출력하는 문제이다.
입력에는 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;
}
'코딩테스트 > 백준' 카테고리의 다른 글
[백준] 10773번 제로 (C++) (0) | 2024.12.17 |
---|---|
[백준] 에디터 (C++) (0) | 2024.12.16 |
[백준] 13300번 방 배정 (C++) (3) | 2024.12.03 |
[백준] 3273번 두 수의 합 (C++) (0) | 2024.12.03 |
[백준] 1475번 방 번호 (C++) (0) | 2024.12.03 |