글 읽기 - Linked List로 구현했는데 반례를 찾지 못하겠습니다. 도움부탁드립니다.

shfshfdl 5년 전 1

안녕하세요 우선 기본 테스트 케이스 및 여러 케이스 테스트시는 동작합니다.

그런데 Linked List로 구현했는데 시작하자 마자 틀렸습니다가 뜹니다.

링크드 리스트를 연결할때 뭔가 끊기거나 한것 같은데 찾지를 못하겠습니다.

도움 부탁드리겠습니다.

_ -> B -> A -> P -> C -> !

와 같이 커서의 위치가 필요해 앞에 _ 마지막에 !를 추가했고

delete시는 커서 앞을 삭제하게 했습니다. 물론 _예외처리를 했구요

add 는 애를 먹어서 여기가 틀렸을 것 같은데 감이 오지 않습니다..

도움부탁드리겠습니다. :(

감사합니다.

#include <stdio.h>
using namespace std;
#define MXL 1000005
int N;
struct NODE {
	NODE *prev, *next;
	char c;
};
struct LIST {
	NODE *head, *tail, *cursor;
};

LIST l;

char str[MXL];

NODE * newPassword(char c) {
	NODE * node = new NODE();
	node->c = c;
	node->next = NULL;
	node->prev = NULL;
	
	return node;
}

void addPassword(NODE * node) {
	if (l.cursor == NULL) {
		l.head = node;
		l.tail = node;
		l.cursor = node;
	} else {
		if (l.cursor->c == '_') {
			node->next = l.cursor->next;
			node->prev = l.cursor;
			if (l.cursor->next != NULL) {
				l.cursor->next->prev = node;
			}
			l.cursor->next = node;
			l.cursor = node->next;
		} else {
			node->next = l.cursor;
			node->prev = l.cursor->prev;
			if (l.cursor->prev != NULL) {
				l.cursor->prev->next = node;
			} else {
				l.head = node;
			}
			l.cursor->prev = node;
		}
	}
}

void moveCursor(char c) {
	switch (c) {
	case '<':{
		if (l.cursor->prev != NULL) {
			l.cursor = l.cursor->prev;
		}
	}break;
	case '>':{
		if (l.cursor->next != NULL) {
			l.cursor = l.cursor->next;
		}
	}break;
	}
}

void deleteAheadCursor() {
	if (l.cursor->prev != NULL && l.cursor->prev->c != '_') {
		l.cursor->prev->prev->next = l.cursor;
		NODE * d = l.cursor->prev;
		l.cursor->prev = l.cursor->prev->prev;
		delete d;
	}
}

void init() {
	l.head = NULL;
	l.tail = NULL;
	l.cursor = NULL;
	// 뒤
	addPassword(newPassword('!'));
	// 앞
	addPassword(newPassword('_'));
}

void printAns() {
	l.cursor = l.head->next;
	while (l.cursor->c != '!') {
		printf("%c", l.cursor->c);
		l.cursor = l.cursor->next;
	}
	puts("");
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		init();

		scanf("%s", str);
		int s = 0;

		while (str[s] != '\0') {
			switch (str[s]) {
			case '<':
			case '>':moveCursor(str[s]); break;
			case '-':deleteAheadCursor(); break;
			default:addPassword(newPassword(str[s])); break;
			}
			s++;
		}
		printAns();
	}

	return 0;
}

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

문제

문제

출처

ICPC

Linked List로 구현했는데 반례를 찾지 못하겠습니다. 도움부탁드립니다.

shfshfdl 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말