글 읽기 - 저지서버에서 오랜 시간후에 '시간초과' 되는데.. 이유를...모르겠습니다 ㅠ

bethebiggreen 8년 전 0

안녕하세요. 늘 많은 도움 받고 있는데, 또 도움을 요청하려 이렇게 올리네요.

나름 속도를 위해서, prev_idx, next_idx 배열을 둬서, 폭발이 일어난 직후, 폭발문자를 제외하고

앞뒤를 링크드 리스트 형식으로 연결하였습니다.

이후, 최종 출력은 next_idx 만 추적하여 출력하였는데, 저지서버에서 정답이 안뜨네요 : (

혹시, 출력문에서 시간이 많이 걸리는건 아닌가 해서

cout -> printf -> 모아서 한번에 버퍼로 담아두고 printf 로 변경해봤지만...

달라지지 않네요.

고수님들의 의견 부탁드려요!

#include <iostream>
#include <cstdio>

using namespace std;

const int MAX_STR_LEN = 1000000;
const int MAX_EXPLOSION_LEN = 36;

char str[MAX_STR_LEN + 3];
char explosion[MAX_EXPLOSION_LEN + 1];
int next_idx[MAX_STR_LEN + 2];
int prev_idx[MAX_STR_LEN + 2];
int exp_size = 0;

void input_proc(void)
{
#if _DEBUG
	freopen("input.txt", "r", stdin);
#endif

#if 0
	cin >> str+1;
	cin >> explosion;
#else
	scanf("%s", str + 1);
	scanf("%s", explosion);
#endif
	while (explosion[exp_size++]);
	exp_size--;
	for (int i = 0; i < MAX_STR_LEN; i++) {
		next_idx[i] = i + 1;
		prev_idx[i] = i - 1;
	}
	explosion[exp_size] = -1;
	str[0] = -1;
}

char output[MAX_STR_LEN] = { 0, };
int output_idx = 0;

void output_proc(void)
{
	int cnt = 0;
	while (str[cnt]) {
		if (str[cnt] != -1) {
			output[output_idx++] = str[cnt];
		}
		cnt = next_idx[cnt];
	}

	char frula[6] = "FRULA";
	frula[5] = '\0';
	cnt = 0;
	if (!output_idx) 
		while(frula[cnt] != '\0')
			output[output_idx++] = frula[cnt++];

    printf("%s\n", output);
}

void do_something(void)
{
	int cur = 1;
	while (str[cur]) {
		int exp_cnt = 0;
		if (str[cur] == explosion[exp_cnt]) {
			int tmp = next_idx[cur];
			while (str[tmp] == explosion[++exp_cnt])
				tmp = next_idx[tmp];
			if (exp_size == exp_cnt) {
				next_idx[prev_idx[cur]] = tmp;
				prev_idx[tmp] = prev_idx[cur];
			}
			else {
				cur = next_idx[cur];
				exp_cnt = 0;
				continue;
			}
			exp_cnt = 0;
			int iter = 0;
			while(iter++ < exp_size || -1 != prev_idx[cur])
				cur = prev_idx[cur];
		}
		else {
			cur = next_idx[cur];
		}
	}
}

int main()
{
	input_proc();
	do_something();
	output_proc();
	return 0;
}

pl0892029 8년 전 0

스택으로 짜시면 쉽지 않을까요? 'ㅂ'

bethebiggreen 8년 전 0

pl0892029 님. 답변 감사합니다 : )

제가 링크드 리스트 스타일이라고 표현했지만, 실제 동작은 스택의 그것과 상당히 유사합니다.

폭발물이 의심되는 첫 캐릭터는 이전의 인덱스를 저장하고 진행한후, 폭발물 처리가 끝나면 이전의 인덱스로 돌아옵니다.

이렇게 반복이 되어 가면, 흡사 스택 구조와 유사해 보이는데요.

혹시 말씀해주시는 부분이, 제가 설명 드린 부분과 어떻게 다른지 여쭤봐도 될까요?

pl0892029 8년 전 0

1. 링크드 리스트가 아닌 직접 스택으로 짜보시는걸 추천드리는 의도였습니다.
스택을 이용하게 되면, 현재 위치에서 몇번째 explosion 문자와 비교해야되는지를 O(1)만에 판단할 수 있습니다.
결과값 또한 스택에 있는 원소를 그대로 출력하면 되기 때문이지요.
구현도 쉽고, 가독성도 좋기 때문에 추천드립니다.

2. 현재 코드와 스택의 차이점
do_something() 함수의 현재 동작은 O(LK) (L : 폭발 전 문자열, K : 폭발하는 길이 문자열)로 보입니다.
스택은 이 부분이 O(L)로 변경됩니다. 성능 상에서도 이점이 많아지지요.

+ 아래 코드처럼, 메모리를 많이 잡아먹는 변수는 전역 변수로 빼시거나 동적 할당을 추천드립니다.

    char output[MAX_STR_LEN] = { 0, };

bethebiggreen 8년 전 0

앗!! 친절한 설명 감사드립니다~ 큰 도움이 되었습니다. (ㅎ 깜빡하고 늦게 댓글 다네요 ㅠㅠ)

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

문제

문제

출처

ICPC

저지서버에서 오랜 시간후에 '시간초과' 되는데.. 이유를...모르겠습니다 ㅠ

bethebiggreen 8년 전 0

pl0892029 8년 전 0

bethebiggreen 8년 전 0

pl0892029 8년 전 0

bethebiggreen 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말