[정올 1809] 탑

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&code=1809 

JUNGOL

#include <stdio.h>

struct P {
	int idx;
	int value;
};

int N, result[500010], sp1, sp2, sp_r;
P st1[500010], st2[500010];

void push_back(P d) {
	st1[sp1++] = d;
}
void push_back2(P d) {
	st2[sp2++] = d;
}
P pop() {
	P rt;
	rt.idx = -1;
	rt.value = -1;

	if (sp1 != 0)	return st1[--sp1];
	else			return rt;
}
P pop2() {
	P rt;
	rt.idx = -1;
	rt.value = -1;

	if (sp2 != 0)	return st2[--sp2];
	else			return rt;
}

void Input() {
	scanf("%d", &N);
	P tmp;
	for (sp1 = 0; sp1 < N;) {
		scanf("%d", &tmp.value);
		tmp.idx = sp1;
		push_back(tmp);
	}
}

void Top() {
	P curTop;
	P rightTop;
	while (sp1)	{
		rightTop = pop();
		curTop = pop();

		if (curTop.value == -1) {//나머지 탑들은 전부 0이다.
			result[rightTop.idx] = 0;
			P keepTop;
			while (sp2) {
				keepTop = pop2();
				result[keepTop.idx] = 0;
			}
		}
		else if (curTop.value > rightTop.value) {//결과를 채운다.
			result[rightTop.idx] = curTop.idx + 1;
			P keepTop;
			while (sp2) //앞선 탑(ST2)들 중에도 있는지 확인
			{//ST2는 오름차순 일 수 밖에 없음, pop하면서 높이 만족하면 채우고 아니면 탈출
				keepTop = pop2();
				if (curTop.value > keepTop.value) {
					result[keepTop.idx] = curTop.idx + 1;
				}
				else {
					push_back2(keepTop);
					break;
				}
			}
			push_back(curTop);
		}
		else {//rightTop은 st2에, curTop은 st1에 넣는다.
			push_back2(rightTop);
			push_back(curTop);
		}//같은 높이의 탑은 없다고 가정
	}
}

int main(void) {
	Input();
	Top();
	for (int i = 0; i < N; i++)	{
		printf("%d ", result[i]);
	}
	printf("\n");
	return 0;
}