글 읽기 - 1406번 에디터 문제 질문입니다..

BothEarRim 8년 전 0

지금 진행중인 '바이너리 덱 리스트' 대회의 H번 문제인 1406번 에디터 문제를 아무리 해도 못 맞추고 있습니다.

Double Linked List 를 구현하는 코드를 짰는데, 시간초과가 납니다...

가장 왼쪽 노드의 left pointer와 가장 오른쪽 노드의 right pointer는 자기 자신을 가리키도록 했습니다.

글자 수가 len이면 커서는 len+1 군데에 있을 수 있으므로 empty node를 가장 오른쪽에 하나 더 만들어두고 이를 늘 유지하는 방식입니다.

(iterator의 end() 같은 식으로)

시간이 오래걸릴 부분이 딱히 없어보이는데다가, 직접 파일입출력으로 10만+50만 글자를 테스트 해보아도 답이 바로 나왔습니다.

스스로 만든 테스트 케이스들도 잘 나오고 채점중(50%)까지 가는 걸 보니 대부분의 경우들이 맞게 나오는 것 같습니다.

어디가 문제일까요..? 혹시 포인터 부분 처리를 잘못해서 while에서 무한루프가 발생하는 걸까요?

도와주시면 정말 감사하겠습니다.

https://www.acmicpc.net/board/view/359

코드는 짜면서 위 링크의 글을 참고했습니다.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#include <iomanip>
#include <string>
#include <cstdlib>
#include <utility>
#include <locale>
#include <queue>
#include <stack>
#include <list>
#include <climits>
#include <cfloat>
#include <map>
#include <functional>
using namespace std;

class Node
{
public:
	Node(char c_=0):c(c_)
	{ l = r = this; };
	char c;
	Node* l;
	Node* r;
};

int main() // H번 - 에디터
{
	char ini[100005], qu[5], letter[5];
	int qu_N;

	scanf("%s\n%d", ini, &qu_N);

	Node* dlist = new Node[strlen(ini)+1];
	for(int i=0; i<=strlen(ini); i++) // 초기 문자열 길이 끝에 하나 더 넣어준다 (커서가 있을 수 있는 공간은 하나 더 많으므로 편의상)
	{
		dlist[i].c = ini[i];
		dlist[i].l = i? &dlist[i-1] : &dlist[i];
		dlist[i].r = i<strlen(ini)? &dlist[i+1] : &dlist[i];
	}

	Node* pt = &dlist[strlen(ini)];
	for(int q=0; q<qu_N; q++)
	{
		scanf("%s", qu);
		if(strcmp(qu, "P")==0)
		{
			scanf("%s", letter);

			Node* newNd = new Node(letter[0]);

			if(pt->l != pt) // 가장 왼쪽에 위치하지 않는 경우엔 왼쪽 노드와 연결시킨다
			{
				pt->l->r = newNd;
				newNd->l = pt->l;
			}

			pt->l = newNd; // 현재 노드(=새로운 노드의 오른쪽)와 연결시킨다
			newNd->r = pt;
		}
		else if(strcmp(qu, "L")==0) pt = pt->l;
		else if(strcmp(qu, "D")==0) pt = pt->r;
		else // "B"
		{
			if(pt != pt->l) // 가장 왼쪽이면 무시하고 아니라면 지울 것이다
			{
				if(pt->l->l == pt->l) pt->l = pt; // 바로 왼쪽 노드가 가장 왼쪽 노드이므로 현재 노드를 그냥 자기자신을 가리키도록 한다
				else // 왼쪽의 왼쪽 노드와 현재 노드를 연결시킨다
				{
					pt->l->l->r = pt;
					pt->l = pt->l->l;
				}
			}
		}
	}

	while(pt != pt->l) pt = pt->l; // 커서를 제일 왼쪽으로 옮긴다
	while(pt != pt->r) // 제일 오른쪽까지 가면서 출력
	{
		printf("%c", pt->c);
		pt = pt->r;
	}
	printf("\n");

    return 0;
}

yukariko 8년 전 1

https://www.acmicpc.net/wiki/도움말

문자열 길이 만큼 반복하기를 읽어보세요

BothEarRim 8년 전 0

덕분에 맞췄습니다! 감사합니다!!

그렇다면, 웬만하면 strlen()은 따로 변수에 저장해 두는 습관을 기르는 게 좋을 것 같네요.

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