07.05. 에디터 [Linked List][백준 1406]

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

1406번: 에디터

 

Algorithm classification : Linked List, Data Structure, Stack

 

07.05.1. Problem

You are given a text that is a sequence of characters.

 

Cursor can be positioned inside of the text (between any two consecutive characters), at the beginning (left of the first character) or at the end (right of the last character) of the text.

You are given sequence of operations you must perform on the text. 

 

Possible operations are: 

L	move cursor one character to the left (if cursor is at the beginning, do nothing)
D	move cursor one character to the right (if cursor is at the end, do nothing)
B	delete character left of the cursor (if cursor is at the beginning, do nothing)
P $	adds the character $ to the left of the cursor

 

Before execution of given operations, cursor is at the end of the text.

Write a program that will determine what would the text look like after execution of given operations. 

 

 

07.05.2. Input limit

In the first row there is the text. It consists only of lowercase letters of English alphabet and its maximal length is 100,000 characters.

 

In the next row there is an integer N, 1 ≤ N ≤ 500,000, number of given operations. 

In the next N rows there are operations given in the order of execution. 

 

 

07.05.3. Output

In first and only row you should write text after the execution of all the operations. 

 

 

07.05.4. Solution

연결 리스트를 배우면 한번쯤은 만나볼 좋은 문제입니다. 중요한 것은 cursor pointer가 2개 필요하다는 것입니다. 저도 엄청 옛날에 풀어서 그냥 예전에 푼 code를 긁어왔습니다. 이제 이런 문제를 풀고 있을 시간은 없습니다.

 

아주 깔끔하군요. 만족스럽습니다. 이때는 비교적 정신이 맑았나보네요.

#include <cstdio>
#include <stack>
#include <stdio.h>
using namespace std;

stack<char> s1, s2;
char buff[6000000];
int n;

int main( void ) {
  scanf("%s", buff);
  scanf( "%d", &n );

  for( char *c = buff; *c; c++ ) s1.push( *c );

  for( int i = 0; i < n; ++i ) {
    scanf( "%s", buff );
    if( buff[0] == 'L' ) {
      if( s1.empty() ) continue;
      s2.push( s1.top() );
      s1.pop();
    }
    if( buff[0] == 'D' ) {
      if( s2.empty() ) continue;
      s1.push( s2.top() );
      s2.pop();
    }
    if( buff[0] == 'B' ) {
      if( s1.empty() ) continue;
      s1.pop();
    }
    if( buff[0] == 'P' ) {
      scanf( "%s", buff );
      s1.push( buff[0] );
    }
  }

  while( !s1.empty() ) {
    s2.push( s1.top() );
    s1.pop();
  }
  while( !s2.empty() ) {
    printf( "%c", s2.top() );
    s2.pop();
  }
  printf( "\n" );

  return 0;
}

 

예전에도 node와 list를 하나씩 다 구현한 흔적이 있더군요. 위의 code를 먼저 제출하고 몇분 뒤에 아래 code를 제출한 흔적이 있었습니다. 그때는 비교적 정신차리고 공부했나보군요.

typedef struct Node{
	int data;
	struct Node* prev;
	struct Node* next;
}NODE;

typedef struct List{
	int count;
	int check;
	struct Node* cursor;
	struct Node* head;
}LIST;

 

LIST* createList(){
	LIST* newList = (LIST *)malloc(sizeof(LIST));
	if(newList == NULL)
		return NULL;
	newList->count = 0;
	newList->check = 0;
	newList->cursor = NULL;
	newList->head = NULL;
	
	return newList;
}

void addNode(LIST* list, int item){
	NODE *newNode = (NODE*)malloc(sizeof(NODE));

	newNode->data = item;
	newNode->next = NULL;
	newNode->prev = NULL;
	if(list->count <= 0){
		list->head = newNode;
		list->cursor = list->head;
	}
	else if(list->check == 0){
		newNode->next = list->head;
		list->head = newNode;
		newNode->next->prev = newNode;
		list->cursor = list->head;
	}
	else{
		newNode->next = list->cursor->next;
		newNode->prev = list->cursor;
		newNode->prev->next = newNode;
		if(newNode->next!=NULL)
			newNode->next->prev = newNode;
		list->cursor = newNode;	
	}
	list->check = 1;
	list->count++;
}

bool removeNode(LIST* list){
	NODE *oldNode = (NODE*)malloc(sizeof(NODE));
	if(list->check == 0) return true;
	if(list->cursor == list->head){
		oldNode = list->head;
		if(list->head->next!=NULL)
			list->head = list->head->next;
		if(list->head!=NULL)
			list->cursor = list->head;
		list->head->prev = NULL;
		free(oldNode);
		list->check = 0;
	}
	else{
		oldNode = list->cursor;
		list->cursor->prev->next = list->cursor->next;
		if(list->cursor->next!=NULL)
			list->cursor->next->prev = list->cursor->prev;
		list->cursor = list->cursor->prev;
		free(oldNode);	
	}
	list->count--;
	return true;
}

void traverse(LIST* list){
	NODE* curNode = list->head;
	while(curNode != NULL && list->count!=0){
		printf("%c",curNode->data);
		curNode = curNode->next;
		//list->count--;
	}
}

void destroyList(LIST* list){
	NODE *oldNode;
	while(list->count){
		oldNode = list -> head;
		list->head = oldNode->next;
		free(oldNode);
		list->count--;
	}
	free(list);
}

 

int main()
{
	LIST* list = createList();
	int i, m;
	char s[100010] = {0}, c;
	scanf("%s", s);
	for(i = 0; s[i]; i++){
		addNode(list, s[i]);
	}
	//traverse(list);
	scanf("%d", &m);
	for(i = 0; i < m; i++){
		scanf(" %c", &c);
		if(c == 'L'){
			if(list->cursor->prev != NULL) list->cursor = list->cursor->prev;
			else list->check = 0;	
		}
		if(c == 'D'){
			if(list->cursor->next != NULL && list->check != 0) list->cursor = list->cursor->next;
			list->check = 1;	
		}	
		if(c == 'B')
			if(list->cursor != NULL) removeNode(list);
		if(c == 'P'){
			scanf(" %c", &c);
			addNode(list, c);
		}
		//printf("cursor : %c //", list->cursor->data);
		//traverse(list);
	}
	traverse(list);

	destroyList(list);
	return 0;
}

 

아마 첫번째 code가 메모리랑 시간을 확실히 덜 잡아먹긴 할겁니다. 하지만 두번째 code처럼 한번 작성해보는 것도 처음 연결 리스트를 배우는 분들에겐 좋은 경험치가 될 것입니다.