백준[1406] 에디터

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

1406번: 에디터

풀이 방법 첫 번째: linked list로 구현.

두 번째: stack로 구현

세 번째: list로 구현

 

효율성은 stack > list > linked list 순으로 좋다.

 

1. stack의 풀이는 두 개의 stack을 만들어서 커서 기준으로 좌측은 s1, 우측은 s2로 저장한다.

2. list는 풀이가 조금 어렵다. dat, pre, nxt라는 배열을 만들고 nxt에 따라 값을 출력한다. dat는 입력된 char들을 순서대로 저장해놓은 배열이다. nxt는 해당 커서에 몇 번째 dat를 출력해야하는지에대한 정보이다. pre는 이전에 출력해야할 char의 index정보이다. dat[0]은 항상 -1이고 dat[1]부터 출력한다. 예를 들어 dat가 -1,a,b,c,d이고 nxt가 1,2,4,-1,3이면 출력은 abdc이다.

3. lined list는 말 그대로 lined list를 구현하면 된다.

 

 

1. 스택 풀이

// stack 풀이
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	string s;
	vector<char> left, right;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		left.push_back(s[i]);
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		char cmd;
		cin >> cmd;
		switch (cmd) {
		case 'L':
			if (!left.empty()) {
				right.push_back(left.back());
				left.pop_back();
			}
			break;
		case 'D':
			if (!right.empty()) {
				left.push_back(right.back());
				right.pop_back();
			}
			break;
		case 'B':
			if (!left.empty()) {
				left.pop_back();
			}
			break;
		case 'P':
			char c;
			cin >> c;
			left.push_back(c);
			break;
		}
	}
	for (int i = 0; i < left.size(); i++) {
		cout << left[i];
	}
	while (!right.empty()) {
		cout << right.back();
		right.pop_back();
	}

	return 0;
}

 

 

2. list 풀이 출처: https://www.acmicpc.net/source/43759918

백준에서 로그인을 한 뒤에 이 문제를 풀어야 링크가 열린다.

로그인

 

3. linked list 풀이.

#include <iostream>
#include <string>

using namespace std;

typedef struct Char {
	char c;
	Char* left;
	Char* right;
}Char;

// 어떤 문자를 가르키는 것은 그 문자 바로 오른쪽에 커서가 있는 것.
// 맨 앞에 보이지 않는 가상의 문자를 두어야 할것.
// left == null이면 첫 문자. 첫 문자는 c == 0이다.
// right == null이면 커서가 맨 뒤에 있다는 뜻.

int main() {
	string s;
	Char firstChar;
	firstChar.c = NULL;
	firstChar.left = NULL;
	firstChar.right = NULL;
	Char* cursor = &firstChar;
	int n;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		Char* c = new Char();
		c->c = s[i];
		c->left = cursor;
		c->right = NULL;
		cursor->right = c;
		cursor = c;
	}
	cin >> n;

	for (int i = 0; i < n; i++) {
		char command;
		cin >> command;
		switch (command) {
		case 'L':
			if(cursor->c != NULL)
				cursor = cursor->left;
			break;
		case 'D':
			if (cursor->right != NULL)
				cursor = cursor->right;
			break;
		case 'B':
			if (cursor->left != NULL) {
				cursor = cursor->left;

				cursor->right = cursor->right->right;
				if (cursor->right != NULL)
					cursor->right->left = cursor;
			}
			break;
		case 'P':
			char t;
			cin >> t;
			Char* insert = new Char();
			insert->c = t;
			insert->left = cursor;
			insert->right = cursor->right;
			if (cursor->right != NULL) {
				cursor->right->left = insert;
			}
			cursor->right = insert;
			cursor = insert;
			break;
		}
	}

	cursor = firstChar.right;
	while (cursor != NULL) {
		cout << cursor->c;
		cursor = cursor->right;
	}

	return 0;
}