글 읽기 - 이건 어떻게 해야하는 건가요?

bangbadak 4년 전 0

맞긴 한 것 같은데 시간 초과가 떠서 질문합니다.

30, 39줄에 주소 변수인 it를 cur 크기만큼 올리는데 저런 반복문 없이 그냥 할 수 있는 건 없나요?

#include<iostream>
#include<list>
#include<algorithm>
#include<cstring>
using namespace std;
int main(void)
{
	int i, j, cur, N, max;
	char ss[600001], co, P;
	list<char> s(600001);
	auto it = s.begin();
	cin >> ss;
	for (i = 0, it = s.begin(); i < (unsigned int)strlen(ss); i++, it++)
		*it = ss[i];
	cin >> N;
	cur = strlen(ss);
	max = strlen(ss);
	for (i = 0; i < N; i++)
	{
		it = s.begin();
		cin >> co;
		if (co == 'L')
			cur > 0 ? cur-- : 0;
		else if (co == 'D')
			cur < max ? cur++ : 0;
		else if (co == 'B')
		{
			if (cur > 0)
			{
				for (j = 0; j < cur - 1; j++)
					it++;
				s.erase(it);//it - 1
				max--, cur--;
			}
		}
		else if (co == 'P')
		{
			cin >> P;
			for (j = 0; j < cur; j++)
				it++;
			s.insert(it, P);
			max++, cur++;
		}
	}
	it = s.begin();
	for (i = 0; i < max; i++, it++)
		cout << *it;
}

nahwasa 4년 전 1

s.erase와 s.insert가 O(n)이 걸립니다.

이 문제는 모든 명령어를 O(1)로 처리할 수 있어야 통과할 수 있습니다.

보통 스택이나 DoublyLinkedList를 사용합니다. (둘다 시간내에 통과 가능)

O(1) 구현은 직접 해보셔요!

bangbadak 4년 전 0

어찌어찌 해봤는데 런타임 에러가 뜨네요..

왜 뜨는 건가요?

#include<iostream>
#include<list>
#include<algorithm>
#include<cstring>
using namespace std;
int main(void)
{
	int i, j, cur, N, max;
	char ss[600001], co, P;
	list<char> s(600001);
	auto it = s.begin(), aml = s.begin();
	cin >> ss;
	for (i = 0, it = s.begin(); i < (unsigned int)strlen(ss); i++, it++)
		*it = ss[i];
	s.resize(strlen(ss));
	cin >> N;
	cur = strlen(ss);
	max = strlen(ss);
	it = s.end();
	for (i = 0; i < N; i++)
	{
		cin >> co;
		if (co == 'L')
			it != s.begin() ? it-- : aml;
		else if (co == 'D')
			it != s.end() ? it++ : aml;
		else if (co == 'B')
		{
			if (it != s.begin())
			{
				s.erase(it);//it - 1
				max--;
			}
		}
		else if (co == 'P')
		{
			cin >> P;
			s.insert(it, P);
			max++;
		}
	}
	it = s.begin();
	for (i = 0; i < max; i++, it++)
		cout << *it;
}

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

문제

문제

출처

ICPC

이건 어떻게 해야하는 건가요?

bangbadak 4년 전 0

nahwasa 4년 전 1

bangbadak 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말