글 읽기 - 다른 반례로는 뭐가 있을까요?

omnix 6년 전 0

양방향 리스트를 구현하고

이 리스트에 문자를 삽입하는 함수와 삭제하는 함수를 각각 하나씩 구현하는 방법으로 문제를 풀어보려고 했습니다.

'|'를 커서가 있을 수 있는 위치라고 하면 abcd는

|a|b|c|d|

이렇게 표현할 수 있는데, 웬지 헷갈리는 것 같아서

(null문자) | a | b | c | d |

위와 같이 맨 앞에 널문자 한개가 있다고 가정했습니다. (그리고 editor구조체의 head포인터가 널문자를 포함한 노드를 가리키게 했습니다)

이를 바탕으로

제가 생각해 볼 수 있는 상황은 전부 시도해 본 것 같은데... 잘 안되네요

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

typedef struct _node {
	char data;
	struct _node* left;//왼쪽
	struct _node* right;//오른쪽
}node;                //노드 구조체

typedef struct _editor {
	node* cursor;//커서
	node* head;//널문자 가리키는 포인터
}editor;                //리스트 구조체

void append_node(editor* E,char data)    //노드를 삽입하는 함수
{
	node* new = (node*)malloc(sizeof(node));
	new->data = data;
	new->left = NULL;
	new->right = NULL;

	if (E->cursor == NULL)    //커서가 아무것도 가리키지 않을 때(초기 상태)
	{
		E->cursor = new;
		new->left = E->head;
		E->head->right = new;
	}
	else if (E->cursor->right == NULL) //커서가 맨 뒤에 있을 때
	{
		E->cursor->right = new;
		new->left = E->cursor;
		E->cursor = E->cursor->right;
	}
	else                            //커서가 맨 앞 또는 중간에 있을 때
	{
		new->right = E->cursor->right;
		E->cursor->right->left = new;
		
		new->left = E->cursor;				
		E->cursor->right = new;
		E->cursor = E->cursor->right;
	}

}

void del_node(editor* E)        //노드를 삭제하는 함수
{
	if (E->head == E->cursor) //커서가 head와 일치할 때(이 부분은 메인에서 예외처리되어서 수행되지 않는 부분입니다 무시해주세요)
	{
		E->head = E->head->right;
		E->cursor = E->cursor->right;
	}
	else        // 커서가 head와 일치 하지 않을 때
	{
		E->cursor->left->right = E->cursor->right;
		E->cursor = E->cursor->left;
	}
}

void Print(editor* E)    //리스트를 출력하는 함수
{
	node* temp = E->head;
	if (temp->right != NULL)temp = temp->right;//head는 널문자를 가리키기 때문에 head 바로 뒤쪽부터 출력합니다
	while (temp != NULL)
	{
		printf("%c", temp->data);
		temp = temp->right;
	}
	printf("\n");
}



int main(void) //메인
{
	editor* E = (editor*)malloc(sizeof(editor));    //에디터 동적할당
	E->cursor = NULL;
	E->head = (node*)malloc(sizeof(node));
	E->head->data = '\0';
	E->head->left = NULL;
	E->head->right = NULL;    //초기화

	char* string = (char*)malloc(sizeof(char) * 100001);//처음 입력받는 문자열 동적할당
	char c;
	while (1)    //리스트에 옮겨적는 부분입니다
	{
		scanf("%c", &c);
		if (c == '\n')break;

		append_node(E, c);
	}

	int N;    
	scanf("%d", &N);

	for (int n = 0; n < N; n++)    //N 번 만큼 명령을 수행
	{
		char command;
		scanf(" %c", &command);

		switch (command) //명령
		{
		case 'L': { //커서 왼쪽이동
			if (E->cursor->left!= NULL && E->cursor!=NULL) //맨 왼쪽이 아니면
			{
				E->cursor = E->cursor->left;//왼쪽으로 이동
			}
		}; break;
		case 'D': {//커서 오른쪽 이동
			if (E->cursor->right != NULL && E->cursor!=NULL)//맨 오른쪽이 아니면
			{
				E->cursor = E->cursor->right;//오른쪽으로 이동
			}
		}; break;
		case 'B': {
			if (E->cursor->data != '\0' && E->cursor!=NULL)//커서가 head와 일치하지 않으면
			{
				del_node(E);//노드 삭제
			}
		}; break;
		case 'P': {
			char data;
			scanf(" %c", &data);//데이터 입력
			append_node(E, data);//입력받은 데이터의 노드 추가
		}; break;
		}
	}

	Print(E); //결과 리스트 출력
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다른 반례로는 뭐가 있을까요?

omnix 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말