백준 boj 1406번 에디터 문제 또 시간초과ㅜ vector코드 있음

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int init_vec(vector<char>& vec)
{
	string str = "";
	cin >> str; // abcd
	int ind = 0;
	int len = str.size();
	while (ind < len)
	{
		vec.push_back(str[ind]);
		ind++;
	}
	return (ind);
}

int main(void)
{
	vector <char> vec;
	int len = init_vec(vec);
	int n;
	cin >> n; //3
	int ind = len; // ind = current index len = vector size
	for (int i = 0; i < n; i++)
	{
		char c;

		cin >> c;
		if (c == 'P')
		{
			char addchar;
			cin >> addchar; // '$'
			vec.insert(vec.begin() + ind, addchar);
			len = vec.size();
			ind += 1;
			//cout << ind;
		}
		else if (c == 'L')
		{
			if (ind != 0)
				ind -= 1;
		}
		else if (c == 'D')
		{
			if (ind != len)
				ind += 1;
		}
		else if (c == 'B')
		{
			if (ind != 0)
			{
				vec.erase(vec.begin() + ind - 1);
				len = vec.size();
				ind -= 1;
			}
		}
		
	}
	for (int i = 0; i < vec.size(); i++)
		cout << vec[i];
	printf("\n");
}

처음엔 벡터로 풀었다. 

vector이란 C언어의 배열처럼 고정된 칸을 부여하지 않아도 되는 동적 배열인데

더하고 삭제하는 것도 용이한 점에서 배열 대신 쓸 수 있는 자료구조다. 

 

다만 더하고 삭제할 때 vec.begin()이라는 벡터 iterator 를 사용해야 하는데 

이 때문에 O(n)이 반복되어 계산되어 시간초과가 났다ㅜㅜㅜㅜ 

 

때문에 벡터 말고 다른 자료구조를 사용해야 하는 상황 

 

결론 : 문제는 없는데 시간초과 때문에 fail한 코드 

 

그래도 vector를 매개변수로 쓸 때 어케 해야하는지 배웠으니까 후횐 없다. 

 

function(v1) 이렇게 소환해도 function(vector<char> & v1) 일케 &문자를 써야 함수 매개변수로 사용 가능 !!!!!

 

도움된 사이트 

[C++ STL] vector

 

 

 

문제를 풀기 위해 

list 맨뒤에서만 삽입 삭제 연산할 수 있는 알고리즘 / 한가운데 원소 삽입하거나 삭제 했을 때 바로 앞 뒤 원소 의외 원소 건드릴 필요가 없는 자료구조 사용 ... 

 

결국에 링크드리스트 사용해야 할듯 

 

#include <iostream>
#include <cstring>
using namespace std;

struct Node {
	char ch;
	Node* next;
	Node* prev;
};

Node *head;
Node* tail;
Node* cursor;
Node *st;
Node *en;

void add_node(char c)
{
	if (head == NULL)
	{
		head = new Node();
		st = new Node();
		en = new Node();
		head->prev = st;
		st->next = head;
		head->next = en;
		en->prev = head;
		st->prev = en->next = NULL;
		head->ch = c;
		tail = head;
	}
	else
	{
		Node *temp = new Node(); 
		temp->ch = c;
		temp->next = tail->next;
		temp->prev = tail;
		tail->next = temp;
		tail = temp;

	}
}

int main(void)
{
	char arr[600001];
	cin >> arr;
	for (int i = 0; i < 600000; i++)
	{
		if (arr[i] == '\0') break;
		add_node(arr[i]);
	}

	int n;
	cin >> n;
	for (int i = 0; i < n;i++)
	{
		char c;
		cin >> c;
		if (c == 'P')
		{
			char addchar;
			cin >> addchar;
			add_node(addchar);
			head = st->next;
		}
		else if (c == 'L')
		{
			//cout << tail->ch;
			if (tail != st)
			{
				tail = tail->prev;
			}
			//cout << tail->ch<<endl;
		}
		else if (c == 'D')
		{
			if (tail->next != en)
			{
				tail = tail->next;
			}
		}
		else if (c == 'B')
		{
			if (tail != st)
			{
				tail->prev->next = tail->next;
				tail->next->prev = tail->prev;
				tail = tail->prev;
				head = st->next;
			}
		}
		
	}
	for (Node* p = head; p != NULL && p->ch != '\0'; p = p->next)
	{
		cout << p->ch;
	}
	printf("\n");
}

이것저것 예제 해봤는데.. 

왜 안될까 ㅜㅜ 

 

abcd
5
L
B
D
B
B

정답: a
출력: ab

 

/*
abcde
5
L
L
L
L
P c

answer: acbcde
output: cabcd

 

여러 반례 보고 다시 고쳤는데 ㅜ 

 

일단 복잡하긴 하지만 후.. 

 

#include <cstdio>
#include <string>
#include <iostream> 
#include <list>
using namespace std;
int n, k;
string s;
char temp, _plus;
list<char> L;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> s >> n;
    for (char c : s) L.push_back(c);
    auto pos = L.end();
    for (int i = 0; i < n; i++) {
        cin >> temp;
        if (temp == 'P') {
            cin >> _plus;
            L.insert(pos, _plus);
        }
        else if (temp == 'L') {
            if (pos != L.begin()) pos--;
        }
        else if (temp == 'D') {
            if (pos != L.end()) pos++;
        }
        else if (temp == 'B') {
            if (pos != L.begin()) {
                pos--;
                pos = L.erase(pos);
            }
        }
    }
    for (char c : L) cout << c;
    return 0;
}

다른 사람 코드 참고 했는데 음 일단 깔끔하다ㅜㅜ 부럽 

 

m.blog.naver.com/jhc9639/221582231149

BOJ 백준 1406번 에디터 #링크드리스트

#include <iostream>
using namespace std;

struct node {
	char value;
	node* left;
	node* right;
};

node* head;
node* last;
node* now;

void addnode(char value) {
	if (head == NULL) {
		head = new  node();
		head->value = value;
		last = head;
		now = head;
	}
	else {
		last->right = new node();
		last = last->right;
		last->value = value;
		last->left = now;
		now = last;
	}
}

void deletenode(node* temp) {
	if (temp->left != NULL) temp->left->right = temp->right;
	else head = head->right;

	if (temp->right != NULL) temp->right->left = temp->left;
}

void insertnode(node* temp, int value) {
	node* p = head;
	if (temp->left == NULL) {
		head = new node();
		head->value = value;
		head->right = p;
		temp->left = head;
	}
	else {
		node* tmp = new node();
		node* tmp1 = temp->left;

		tmp->value = value;

		temp->left = tmp;
		tmp->right = temp;
		tmp->left = tmp1;
		tmp1->right = tmp;
	}
}

int main() {
	char arr[600001], cmd1, cmd2;
	int num;
	cin >> arr;

	for (int i = 0; i < 600000; i++) {
		if (arr[i] == '\0') break;
		addnode(arr[i]);
	}
	addnode('\0');

	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> cmd1;
		if (cmd1 == 'P') cin >> cmd2;

		switch (cmd1) {
		case 'L':
			if (now->left == NULL) continue;
			now = now->left;
			break;
		case 'D':
			if (now->right == NULL) continue;
			now = now->right;
			break;
		case 'B':
			if (now->left == NULL) continue;
			deletenode(now->left);
			break;
		case 'P':
			insertnode(now, cmd2);
			break;
		}
	}

	for (node* p = head; p != NULL; p = p->right)
	{
		cout << p->value;
	}

	return 0;
}

    
    /*
	node* p = head;
	while (1) {
		if (p == NULL || p->value == '\0') break;
		cout << p->value;
		p = p->right;
	}*/

이건 나랑 비슷하게 짠 코드 

start end 따로 안 만들고 NULL로만 처리 해도 된다.