백준 11003 C - stack

i - L + 1 ~ i 까지의 수 중 가장 작은 값을 출력하기만 하면 되는 아주 간단한 문제이다.

하지만 N과 L이 최대 5e6이라는 점을 감안하면, 단순히 배열을 하나하나 탐색한다면 최악의 경우 2.5e12 의 

연산이 필요하여 필연적으로 시간초과가 뜬다.

 

하여 필요한 연산은 Nlog(2)L 혹은 N 정도에 끝내야한다.

 

여기서 나는 STACK 을 약간 응용하여 시작점이 움직이는 스택을 생각해서 써봤다.

편의상 Moving Stack이라고 부르겠다.

 

일반적인 Stack이 (C에서 리스트로 구현할 경우) Writing point 만 움직이면서 쓸지말지를 결정한다면,

Moving Stackd은 Reading point 도 같이 움직이면서 Stack 의 시작점을 정한다.

 

예를 들자면 , int Stack[5] 가 있고 , Wp=Rp=0 이라고 가정한다.

그럼 1과 2를 넣을 경우 Wp = 2가 되고 Rp=0 그대로 유지되면서 ,Stack[0]=1, Stack[1] = 2;

가 된다고 약속하자.

만약 이 상황에서 내가 오름차순으로 Stack 에 넣었다면, Stack[Rp(0)] 에 있는 숫자는 항상 최솟값을 가질 것이다.

 

만약 Wp-1 (지금은 1인 상황) 에 있는 숫자가 다음 넣을 숫자보다 크면 어떻게 될까?

다음 넣을 숫자를 1이라고 해보자.

Stack[Wp-1] 과 1을 비교해보니 Stack[Wp-1]가 더 큰 상황이다. 

이럴 경우 오름차순 스택을 유지하기 위해 2를 지우고, 1보다 작은 수가 나올때까지 자리를 찾아본다.

그렇기 때문에 Wp = Wp-1이 되고, 다음 비교는 Stack[0]=1 과 1의 비교가 된다.

 

나의 경우엔 같은 경우에도 빼버린다. (안빼도되지만 index는 갱신해줘야한다. 이해가 안되면 우선 패스)

그러므로 Wp=0 이 되고 스택이 모두 비었으므로 (Rp == Wp) 더 이상 빼지 않고 Stack에 넣어준다.(Stack[0]=1)

 

중요한 것은 

1. 항상 오름차순을 유지하여 Stack[Rp]에 있는 값이 항상 최솟값일 수 있도록

2. 범위 (i-L+1~ i)안에 있는지 index를 계속 확인하여 Stack을 관리해줘야한다.

 

이 경우 최악의 경우에도 2N 에 불과하므로 제한시간안에 들어올 것으로 기대할 수 있다. (2.4초)

메모리도 Stack 과 최솟값이 저장될 배열만 있으면 되므로 60MB 수준을 기대할 수 있다. (제한 512MB);

 

전체 코드

#include <stdio.h>
int N, L;
#define MAX_N 5000000
typedef struct st {
	int index, value;
}STACK;
int Wp, Rp, idx;
STACK stack[MAX_N+1];
int D[MAX_N + 1];


void solve(int i,int a) {
	//맨 먼저 들어간 놈의 인덱스가 범위를 벗어날 경우
	if (stack[Rp].index <= i - L) {
		Rp++;
	}
	while (1) {
		//스택이 비었거나 들어오는 놈(a)가 스택의 탑(마지막요소)보다 큰 경우
		if (Wp == Rp || stack[Wp - 1].value < a) {
			stack[Wp].index = i;
			stack[Wp++].value = a;
			break;
		}
		Wp--;
	}

	D[idx++] = stack[Rp].value;
}

int main() {
	scanf("%d %d", &N, &L);
	int a;
	for (int i = 0; i < N; i++) {
		scanf("%d", &a);
		if (i == 0) {
			stack[Wp].index = 0;
			stack[Wp++].value = a;
			D[idx++] = a;
			continue;
		}
		solve(i,a);
	}
	for (int i = 0; i < N; i++) {
		printf("%d ", D[i]);
	}
	return 0;
}

 

풀면서 문제가 있었던 점은 없었으며, STACK의 응용을 통해 풀어서 간단했다.

물론 실행 시간이 간당간당했다는 점(2300ms, 왜?)이 불안하므로 다른 방식을 찾아보면 좋을 것 같다.

예를 들어 우선순위 큐를 이용한다면 조금 더 단축할 수 있지 않았을까 싶다.(아직 잘모름)