[백준 5397] 키로거 (C++)

풀이

생각보다 고생한 문제!!

 

주어진 문자열의 길이가 100만이기 때문에 여기서 빈번한 삭제와 삽입이 필요하므로

list 자료구조를 이용해야 한다.

 

문제는 list에 대해서 얄팍하게 알고 있다면 크게 디일 수 있다..

 

문제에서는 커서를 이용해서 옮겨 다니며 리스트에 해당 문자를 삽입하거나 삭제하는 구조로 되어있다.

따라서 처음에 cursor를 list의 첫 번째 반복자로 할당해놓고 양방향 반복자이므로 뒤로 갔다 앞으로 갔다 하면서 주어진 문제에 맞게 동작을 처리하면 된다.

 

'<'

cursor 왼쪽으로

if (s[i] == '<')
{
	if (cursor != lt.begin())
		cursor--;
}

'>'

cursor 오른쪽으로

else if (s[i] == '>')
{
	if (cursor != lt.end())
		cursor++;
}

'-'

cursor 한 칸 왼쪽으로 당겨서 지워주고 cursor의 위치를 그 다음 위치로 옮겨야 한다.

문제에서 만약 커서의 위치가 줄의 마지막이 아니라면,

커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동하라는 말이 있다.

else if (s[i] == '-')
{
	if (cursor != lt.begin())
		cursor = lt.erase(--cursor);
}

아무것도 아니라면 list에 삽입해주면 된다.

else
{
	lt.insert(cursor, s[i]);
}

 

헷갈린 나를 위해서 정리본

iter2 = lt.insert(iter1, data);
iter1 자리에 data를 삽입한다.
iter1은 삽입한 다음 위치를 가리킨다.
iter2는 삽입한 그 위치를 가리킨다.

iter2 = lt.erase(iter1);
iter1 자리에 data를 삭제한다.
iter2는 삭제된 다음 위치를 가리킨다.

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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--)
	{
		string s;
		list<char> lt;
		auto cursor = lt.begin();

		cin >> s;

		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] == '<')
			{
				if (cursor != lt.begin())
					cursor--;
			}
			else if (s[i] == '>')
			{
				if (cursor != lt.end())
					cursor++;
			}
			else if (s[i] == '-')
			{
				if (cursor != lt.begin())
					cursor = lt.erase(--cursor);
			}
			else
			{
				lt.insert(cursor, s[i]);
			}
		}

		for (auto c : lt)
			cout << c;
		cout << '\n';
	}
	return 0;
}