[백준 C언어] 1406. 에디터

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

 

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

 

 

나의 풀이

5397번 키로거와 비슷하게 풀이할 수 있는 문제이다.

(* 참고 5397. 키로거 문제 : https://www.acmicpc.net/problem/5397 , 해설 : https://seoyyeong.tistory.com/37)

 

특정 데이터를 기준으로 두고 데이터의 이전, 다음으로 이동이 필요한 문제들은

이중 연결 리스트의 형태로 풀면 간단하다.

명령어인 L, D, B, P에 대응하는 함수를 만들어 주고,

명령어를 읽어올 때마다 함수를 호출하기만 하면 된다. 

 

#include <stdio.h>
#include <stdlib.h>

typedef struct node {		//연결 리스트의 node 구조체
	char key; //문자가 저장될 변수
	struct node* prev, * next; //노드의 왼쪽과 오른쪽 노드 포인터
}node;

node* head, *tail, *p; //리스트의 head, tail, 커서 변수

void init(void) {		//리스트 초기화
	head = (node*)malloc(sizeof(node));
	tail = (node*)malloc(sizeof(node));
	head->prev = head; //head와 tail 연결
	head->next = tail;
	tail->prev = head;
	tail->next = tail;
	p = head; //커서는 head(리스트의 맨 앞)으로 정의
}

void left(void) { // 커서 포인터 왼쪽으로 이동
	if (p != head) { //커서가 head일 때는 더 이상 갈 수 없음
		p = p->prev;
	}
}

void right(void) { //커서 포인터 오른쪽으로 이동
	if (p != tail->prev) { //커서가 문자열의 마지막일 때는 더 이상 갈 수 없음
		p = p->next;
	}
}

void del(void) { //커서 왼쪽(커서 포인터가 가리키는 노드)의 글자 삭제
	if (p != head) { //커서가 맨 왼쪽에 있을 경우 삭제하지 않음
		node* t = p; 
		p = p->prev; //커서 이동
		p->next = t->next; //삭제될 노드의 이전 노드와 다음 노드 연결
		t->next->prev = p;
		free(t); //노드 삭제
	}
}

void insert(char c) { //문자 삽입
	node* n = (node*)malloc(sizeof(node));
	n->key = c;
	n->prev = p; //삽입될 노드와 이전, 다음 노드 연결
	n->next = p->next;
	p->next->prev = n;
	p->next = n;
	p = n; //삽입된 문자로 커서 이동
}

void del_all(void) { //메모리 free
	node* d = head->next;
	while (d != tail) { //head~tail 사이의 노드 모두 삭제
		node* t = d;
		d = d->next;
		free(t);
	}
	free(head); //head, tail노드 삭제
	free(tail);
}

void print(void) { // head~tail 사이의 노드 키값 출력
	node* s = head->next;
	while (s != tail) {
		printf("%c", s->key);
		s = s->next;
	}
}

int main(void) {

	int m;
	char c;
	init();

	while ((c = getchar()) != '\n') //엔터가 입력되기 전까지 문자 저장
		insert(c);

	scanf("%d\n", &m); //명령 개수 읽어오기

	for (int i = 0; i < m; i++) {
		scanf("%c ", &c); //명령 읽어오기
        
        //scanf로 읽어온 문자와 명령 비교
		if (c == 'P') { //삽입
			scanf(" %c", &c);
			insert(c);
		}
		else if (c == 'L') { //왼쪽으로 이동
			left();
		}
		else if (c == 'D') { //오른쪽으로 이동
			right();
		}
		else { //문자 삭제
			del();
		}
	}
	print(); //출력
	del_all(); //할당된 메모리 돌려주기
	return 0;
}

 

 

명령어 판별을 위한 for문 안에서 scanf를 사용할 때,

84번 행과 같이 화이트 스페이스를 사용해 주어야 한다. 

 

명령 이후 들어오는 엔터 또는 스페이스바를 없애주기 위해서이다. 

그렇지 않으면 다음 루프로 넘어갈 때 c에는 엔터 또는 스페이스바가 잡히게 된다. 

화이트 스페이스를 사용하지 않고, 아래와 같이 getchar()를 사용하여 버퍼를 비워주는 방법도 있다.

	for (int i = 0; i < m; i++) {
		scanf("%c", &c);
		if (c == 'P') {
			getchar(); //명령어와 삽입될 글자 사이의 공백 무시
			scanf("%c", &c);
			insert(c);
			getchar(); //다음에 들어오는 엔터 무시
		}
		else if (c == 'L') {
			left();
			getchar();
		}
		else if (c == 'D') {
			right();
			getchar();
		}
		else {
			del();
			getchar();
		}
	}

 

 

(풀어보기 : https://www.acmicpc.net/problem/1406 )