[백준/c++] 5397번 키로거 풀이(실버2)

 

문제

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

5397번: 키로거

 

 

풀이

이 문제는 배열의 중간에서 삽입, 삭제가 빈번하게 일어난다. 따라서 vector나 deque보다 list를 사용하는 것이 효율적이다.

c++에서 list는 linked list를 의미한다. 그래서 배열의 중간 부분을 삽입, 삭제할 때 다른 연속적인 메모리 리스트보다 효율적이다.

 

먼저 문자열을 입력받은 뒤, 입력받은 문자열의 모든 요소를 순차적으로 탐색하여 list에 삽입, 삭제한다.

list는 인덱스를 제공하지 않고 iterator 기능만을 제공한다.

 

 

list.eraser 사용 시 주의할 점

list.eraser(iter)     // 오류

iter = list.eraser(iter)

 

eraser은 삭제된 iterator의 다음 iterator를 반환한다. 그 반환값을 저장해주어야 한다.

 

 

 

코드

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

int main()
{
	int T;
	cin >> T;
	
	for (int i = 1; i <= T; i++) {
		string str1;
		cin >> str1;
		list<char> ps;

		list<char>::iterator iter = ps.begin();

		for (int i = 0; i < str1.size(); i++) {
			switch (str1[i])
			{
			case '<':
				if (iter != ps.begin())
					iter--;
				break;
			case '>':
				if (iter != ps.end())
					iter++;
				break;
			case '-':
				if (iter != ps.begin()){
					iter = ps.erase(--iter);
				}
				break;
			default:
				ps.insert(iter, str1[i]);
				break;
			}
		}

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

	return 0;
}