19. UVa-11988 Broken Keyboard // Unique linked list problem

문제

<그림1: 문제설명>

문제 이해 자체는 어렵지 않다. 우리가 키보드를 칠 때 Home키 누르면 입력중인 text의 맨 앞으로 cursor가 이동하고 End키를 누르면 입력중인 text의 맨 뒤로 cursor가 가게 되는데, 이를 [와]로 표현한 Text가 있는 것이다.

 

따라서 문자를 하나하나 읽으면서 [와 ]이 나올때마다 cursor의 위치를 바꿔야 하는데 이것을 하는 데는 list가 제격인 자료구조다. 풀이는 다음과 같다.

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

int main() {

	string str;

	while (cin >> str&&!cin.eof()) {
		list<char> result;
		list<char>::iterator cursor;
		cursor = result.begin();
		for (int i = 0; i < str.length(); i++) {
			if (str[i] == '[') cursor = result.begin();
			else if (str[i] == ']') cursor = result.end();
			else {
				result.insert(cursor, str[i]);
			}
		}
		for (list<char>::iterator i = result.begin(); i != result.end(); i++) {
			cout << *i;
		}
		cout << endl;

	}
	

	return 0;
}

 

 이 부분이 핵심이다. list의 insert는 현재 iterator의 앞에 삽입한다는 것을 유념하자

if (str[i] == '[') cursor = result.begin();
else if (str[i] == ']') cursor = result.end();
else {
	result.insert(cursor, str[i]);
}