[BaekJoon] 백준 5397번 키로거

백준 5397번 키로거

 

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

 

 

코드

 

-처음에 vector로 풀려고 했더니 계속 시간초과남.

-vector의 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것. 따라서 원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만 insert(), erase(), push_back() 등은 비효율적으로 동작
-원소의 삽입, 삭제가 자유롭고 효과적인 list로 짜야함(stack으로 짠 경우도 있음 https://deliorange.tistory.com/66)

 

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

using namespace std;

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

	int n;
	cin >> n;
	while (n--) {
		string L; 
		cin >> L;
		list<char> arr;
		list<char>::iterator iter = arr.begin();
		int L_len = L.size(), L_idx = 0;

		while (L_idx < L_len) {
			switch (L[L_idx]) {
			case '<':
				if (iter != arr.begin()) iter--;
				break;
			case '>':
				if (iter != arr.end()) iter++;
				break;
			case '-':
				if (iter != arr.begin()) arr.erase((--iter)++);
				break;
			default:
				arr.insert(iter, L[L_idx]);
				break;
			}
			L_idx++;
		}
		for (auto x : arr) printf("%c", x);
		printf("\n");
	}
	return 0;
}

 

 

 

참고

 

http://melonicedlatte.com/algorithm/2018/11/13/003246.html

https://hyeonstorage.tistory.com/324