백준 에디터 (1406번) c++

문제

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

1406번: 에디터

문제 풀이

처음 문제를 보고 나는 vector로 풀까 하고 생각을 했다.

하지만 시간 제한이 0.3초 인걸 확인하고 vector.erase와 vector.insert가 시간초과에 걸릴거 같아 연결리스트로 생각을 바꿨다.

 

vector로 구현한 소스이다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){

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

        string input;

        cin >> input;

        vector<char> li;

        for(register int i = 0; i < input.length(); i++){
                li.push_back(input[i]);
        }

        int cursor = input.length();

        int N;

        cin >> N;

        while(N--){

                char alpha, in;

                cin >> alpha;

//              cout << cursor << '\n';

                switch(alpha){

                        case 'L':
                                if(cursor > 0){
                                        cursor--;
                                }
                                break;

                        case 'D':
                                if(cursor < li.size()){
                                        cursor++;
                                }
                                break;

                        case 'B':
                                if(cursor != 0){
                                        cursor--;
                                        li.erase(li.begin() + cursor);
                                }
                                break;

                        case 'P':
                                cin >> in;
                                li.insert(li.begin() + cursor, in);
                                cursor++;
                                break;

                        default:
                                break;

                }

        }

        for(register int i = 0; i < li.size(); i++){
                cout << li[i];
        }
        cout << '\n';


        return 0;

}

역시 시간초과였다.

vector의 insert나 erase는 O(n) 정도 걸리기 때문에 이 문제에서는 쓸 수 없다.

연결 리스트나 stack은 O(1) 이기 때문에 가능하다.

 

 

Doubly Linked List로 구현하여 B와 P를 해결하려고 했다.

그리고 cursor라는 변수를 통해 cursor를 움직였다.

#include <iostream>
#include <string>

using namespace std;

struct Node{

	char val;
	Node* prev;
	Node* next;

};

Node head_;
Node node[700001];
int node_cnt;
Node* cursor;

void insert(char in){

	node[node_cnt].val = in;
	node[node_cnt].prev = cursor;

	if(!cursor->next){
		cursor->next = &node[node_cnt++];
	}

	else{
		node[node_cnt].next = cursor->next;
		cursor->next->prev = &node[node_cnt];
		cursor->next = &node[node_cnt++];
	}
	cursor = cursor->next;

	return;

}

void delete_node(){

	if(cursor == &head_) return;

	cursor->prev->next = cursor->next;

	if(cursor->next){
		cursor->next->prev = cursor->prev;
	}

	cursor = cursor->prev;

	return;

}

void print_node(){

	Node* present = head_.next;

	while(present){

		cout << present->val;
		present = present->next;

	}

	cout << '\n';

	return;
}

int main(){

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

	string input;

	cin >> input;

	cursor = &head_;

	for(register int i = 0; i < input.length(); i++){
		insert(input[i]);	
	}

	int N;

	cin >> N;

	for(register int i = 0; i < N; i++){

		char alpha, in;

		cin >> alpha;

//		cout << cursor->val << '\n';

		if(alpha == 'L'){
			if(cursor != &head_) cursor = cursor->prev;
		}

		else if(alpha == 'D'){
			if(cursor->next) cursor = cursor->next;
		}

		else if(alpha == 'B'){
			delete_node();
		}

		else if(alpha == 'P'){
			cin >> in;

			insert(in);
		}

	}

	print_node();

	return 0;

}

 

마지막으로 stack을 이용하여 구현할 수도 있다.

두개의 stack이 있다고 생각하고 왼쪽 stack, 오른쪽 stack으로 나누어 생각을 한다.

그리고 cursor의 위치에 따라 왼쪽으로 움직여야 하면 왼쪽 stack 값을 오른쪽 stack으로 옮기고,

오른쪽으로 움직여야 하면 반대로 하면 된다.

 

마지막으로 결과를 출력해야 할 때는 왼쪽 stack의 모든 값을 오른쪽 stack으로 옮겨 하나씩 빼서 프린트 하면 된다.

 

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(){

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

        string input;

        cin >> input;

        stack<char> left, right;

        for(register int i = 0; i < input.length(); i++){
                left.push(input[i]);
        }

        int N;

        cin >> N;

        while(N--){

                char alpha, in;

                cin >> alpha;

                switch(alpha){

                        case 'L':
                                if(!left.empty()){
                                        right.push(left.top());
                                        left.pop();
                                }
                                break;

                        case 'D':
                                if(!right.empty()){
                                        left.push(right.top());
                                        right.pop();
                                }
                                break;

                        case 'B':
                                if(!left.empty()){
                                        left.pop();
                                }
                                break;

                        case 'P':
                                cin >> in;
                                left.push(in);
                                break;

                        default:
                                break;

                }

        }


        while(!left.empty()){
                right.push(left.top());
                left.pop();
        }


        while(!right.empty()){
                cout << right.top();
                right.pop();
        }


        cout << '\n';


        return 0;

}