백준(baekjoon) [C] - 2493번: 탑

https://www.acmicpc.net/problem/2493

2493번: 탑

---

~~ 실패 코드 ~~

#include <stdio.h>  // 탑
#include <stdlib.h>

int arr[500000] = { 0, };


int main()
{
	int n;
	scanf("%d", &n);

	int* ans = malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		ans[i] = 0;

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	for (int i = n - 1; i > 0; i--)
	{
		for (int j = i - 1; j > 0; j--)
		{
			if (arr[j] > arr[i])
			{
				ans[i] = j + 1;
				break;
			}
		}
	}
	
	for (int i = 0; i < n; i++)
		printf("%d ", ans[i]);

	return 0;
}

-- 스택을 어떻게 사용해야할지 딱 떠오르지가 않아서 생각나는대로 구현 --> 시간초과 실패

 

~~ 성공 코드 ~~

 

#include <stdio.h>  // 탑
#include <stdlib.h>

typedef struct
{
	int ptr;
	int** stk;
}STACK;

int is_empty(STACK* s)
{
	if (s->ptr <= 0)
		return 1;
	else
		return 0;
}

void push(STACK* s, int num, int index)
{
	// 숫자와 인덱스 스택에 담기
	s->stk[s->ptr][0] = num;
	s->stk[s->ptr++][1] = index;
}

int top_num(STACK* s)
{
	int temp = s->ptr;
	return s->stk[--temp][0];
}

int top_index(STACK *s)
{
	int temp = s->ptr;
	return s->stk[--temp][1];
}

void pop(STACK* s)
{
	s->ptr--;
}

int arr[500000] = { 0, };


int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	STACK s;
	s.ptr = 0;
	s.stk = malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++)
	{
		s.stk[i] = malloc(sizeof(int) * 2);
	}
	
	printf("%d ", 0);
	for (int i = 0; i < n - 1; i++)
	{
		push(&s, arr[i], i + 1);
		while (1)
		{
			if (is_empty(&s))
			{
				printf("%d ", 0);
				break;
			}
			else if (arr[i + 1] > top_num(&s))
			{
				pop(&s);
			}
			else
			{
				printf("%d ", top_index(&s));
				break;
			}
		}
	}

	return 0;
}

---

MEMO

-- 스택에 탑의 높이(숫자)와 인덱스 같이 담기 --> 2차원 배열로 스택 공간 생성

-- 처음 탑은 무조건 0 출력(레이저 다른 탑에 도달 불가)

-- 스택 top의 높이와 비교해서 탑(A)의 높이가 top보다 더 크다면 pop --> 뒤의 탑(A)이 더 크다는 것은 앞의 탑(top)에 레이저가 도달이 불가능 하다는 것이고, 해당 탑(A)보다 더 뒤에 top 보다 작은 탑이 있다는 점을 고려하더라도 해당 탑의 레이저가 top에 도달하기 전 A에 도달하기 때문에 필요성이 없어지기 때문에 pop실행!! (ex) 5(top) 7(A) 4 의 경우)

 

!! 골드5 문제인데 앞으로는 골드 문제라고 겁먹지 말자 !!