[1406] 에디터 - 연결 리스트 ★☆☆☆ / 복습 ●

[ 문제 ] : https://www.acmicpc.net/problem/1406

1406번: 에디터

---

[ 문제 접근 ]

 

- 연결리스트로 풀어야 겠다 라는 생각을 할 수 있는가가 관건이였다.

---

[ 최종 코드 ]

 

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

using namespace std;

string input = "";
list<char> str;


int main() {
	unsigned int m;
	char order;

	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> input;
	cin >> m;

	// str에 입력한 문자열 넣어주고
	for (size_t i = 0; i < input.length(); i++) {
		str.push_back(input[i]);
	}
	//list<char> str(input.begin(), input.end());  이렇게 해줘도 된다.


	list<char>::iterator cursor = str.end();  // 처음에 커서 뒤에서 부터 시작.

	for (unsigned int i = 0; i < m; i++) {
		cin >> order;
		switch (order)
		{
		case 'L':
			if (cursor != str.begin()) {
				cursor--;
				break;
			}
			break;
		case 'D':
			if (cursor != str.end()) {
				cursor++;
				break;
			}
			break;
		case 'B':
			if (cursor != str.begin()) {
				cursor = str.erase(--cursor); //★★★ 다음 값이 연속된 메모리에 있지 않기에 꼭 cursor로 받아줘야한다 안그러면 오류 난다.
				break;
			}
			break;
		case 'P':
			cin >> order;
			str.insert(cursor, order);
			break;
		}
	}

	for (auto elem : str) cout << elem;

	return 0;
}

[ for 문 이용한 풀이 ]

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

using std::cout; using std::cin;
using std::string;

string str;
int m;

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> str;
	cin >> m;

	string order;
	char input;
	std::list<char> l_str;

	for (auto elem : str) {
		l_str.push_back(elem);
	}

	std::list<char>::iterator cursor = l_str.end();
	

	while (m--) {
		cin >> order;

		if (order == "P") {
			cin >> input;
			l_str.insert(cursor, input);
		}
		else if (order == "L") {
			if (cursor == l_str.begin()) {
				continue;
			}
			cursor--;
		}
		else if (order == "B") {
			if (cursor == l_str.begin()) {
				continue;
			}
			cursor = l_str.erase(--cursor);
		}
		else {
			if (cursor == l_str.end()) {
				continue;
			}
			cursor++;
		}
	}
	for (auto elem : l_str) {
		cout << elem;
	}

	return 0;
}

 

---

[ Key Point ]

 

👉 Vector와 다르게 List 의 erase 함수를 사용할때는 반드시 리턴되는 다음 iterator 값을 받아줘야된다.

cursor = l_str.erase(--cursor);

다음 원소가 메모리 연속된 위치에 있지 않고 힙 어딘가에 있기 때문에 iter 주소를 잃게 된다.

 

👉 List 의 iterator는 벡터와 달리 ++; --; 연산 밖에 안된다.

​

---