글 읽기 - 배열을 활용하여 리스트를 구현하였는데 반례를 모르겠습니다.

dhdbsgn111 4년 전 0

배열을 활용해서 풀었는데 반례를 모르겠습니다.

#include <stdio.h>
#define max 10000
typedef struct node
{
	int child;
	int parent;
	char c;
}node;



int main(void)
{
	node arr[600002];
	arr[600000].child=0; //head
	arr[600000].parent=-1;
	arr[600001].child=-1; //last
	char c[100000];
	int cursor=1;
	scanf("%s",c);
	int l=1;
	arr[0].c=c[0];
	arr[0].parent=600000;
	arr[0].child=1;
	while(1)
	{
		if(c[l]=='\0') break;
		arr[l].c=c[l];
		arr[l].child=l+1;
		arr[l].parent=l-1;
		l++;
		cursor++;
	}
	l--;
	cursor--;
	arr[l].child=600001;
	int T;
	scanf("%d",&T);
	char command;
	char plus[1];
	int i=0;
	int a;
	while(i!=T)
	{
		scanf(" %c",&command);
		if(command=='P')
		{
			l++;
			scanf(" %s",plus);
			arr[l].c=plus[0];
			arr[l].parent=cursor;
			arr[l].child=arr[cursor].child;
			arr[cursor].child=l;
			cursor=arr[cursor].child;
		}
		else if(command=='L')
		{
			
			if(arr[cursor].parent==-1) 
			{	
				i++;
				continue;
			}
			cursor=arr[cursor].parent;
		}
		else if(command=='D')
		{
			if(arr[arr[cursor].child].child==-1)
			{
				i++;
				continue;
			}
			cursor=arr[cursor].child;
		}
		else if(command=='B')
		{
			if(arr[cursor].parent==-1)
			{
				i++;
				continue;				
			}
			arr[arr[cursor].child].parent=arr[cursor].parent;
			arr[arr[cursor].parent].child=arr[cursor].child;
			cursor=arr[cursor].parent;
		}
		i++;
	}
	a=600000;
	while(1)
	{
		a=arr[a].child;
		printf("%c",arr[a].c);
		if(arr[a].child==-1) break;
	}	
	printf("\n");
}

djm03178 4년 전 0

길이가 10만인 문자열을 입력받으려면 배열의 크기는 최소 10만1이 필요합니다.

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

문제

문제

출처

ICPC

배열을 활용하여 리스트를 구현하였는데 반례를 모르겠습니다.

dhdbsgn111 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말