글 읽기 - C 시간초과 질문 (23%)

utoutouto 2년 전 0

node_t 를 원소로 가지는 deque를 설정하고 새로운 값(num)을 받을 때. 아래와 같은 절차대로 업데이트했습니다.

head는 deque의 마지막 부분 인덱스이고, tail은 deque의 첫 부분 인덱스입니다.

- 절차

1. num이 deque의 마지막 값보다 작을 경우, 마지막 값을 없애고 새로운 마지막값과 num을 비교하는 작업을 반복한다.

2. num이 deque의 마지막 값보다 클 경우, 삽입한다.

3. 현재 tail이 num의 인덱스와 l이상 차이나는 경우 한 deque의 앞부분을 제거한다.

아마도 1번에서 시간초과가 나는 것 같은데 최악의 경우에도 O(N²)는 안 날 것 같은데 어떤 문제가 있는지 모르겠습니다.

deque가 정렬되어있으니까 이중분할로 찾아보기도 했는데 그래도 시간초과가 납니다.

#include <stdio.h>

#define SIZE (1 << 19)

typedef struct node {
	int idx;
	int value;
} node_t;

node_t deque[SIZE];
int num_DQ = 0;

int algorithm_11003(void);

int main(void)
{
	algorithm_11003();
	return 0;
}

int algorithm_11003(void)
{
	int n, l;
	scanf_s("%d %d", &n, &l);

	int tail = 0, head = 0;
	for (int i = 0; i < n; i++)
	{
		int num;
		scanf_s("%d", &num);

		// rmeove nodes which are smaller than num.
		while (num_DQ != 0 && deque[head - 1].value > num)
		{
			num_DQ--;
			head--;
		}
		// add new node to the last position of deque.
		{
			deque[head].idx = i; deque[head].value = num;
			head++; num_DQ++;
		}
		// if the node on tail is too old, remove it.
		if (i - deque[tail].idx >= l)
		{
			num_DQ--;
			tail++;
		}
		printf("%d ", deque[tail].value);
	}

	return 0;
}

kdh6429 2년 전 0

최악의 경우에 L M 이 5000000 인 경우를 고려해보면 꽤 많은 탐색을 요구하는 코드입니다.

다른 방식으로 접근을 시도해봐야 할것 같습니다.

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

문제

문제

출처

ICPC

C 시간초과 질문 (23%)

utoutouto 2년 전 0

kdh6429 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말