백준 12015

특정수열값 정렬할 배열을 하나 만들어야함
stack 이용

반복문을 사용
수열의 값이 stack[top]의 값과 비교하는 과정

1. 수열의 값 < stack[top] 이면, 수열의 값보다 ① 크면서 ② 그 중에서 가장 작은 수와 자리를 교체해주는 lower_bound를 해준다.

2. 수열의 값 > stack[top] 이면, push 해준다.

3. 수열의 값 == stack[top] 이면, 이 과정을 뛰어 넘는다. ( = continue )

#include <stdio.h>

#define STACK_SIZE 1000000

int stack[STACK_SIZE];
int top = -1;

int isEmpty()
{
	if (top < 0)
    	return 1;
	else
    	return 0;
}

	int isFull()
		{
        if (top >= STACK_SIZE)
    			return 1;
		else
    		return 0;
	}

void push(int x)
{
	if (isFull() == 0)
    	stack[++top] = x;
}

int pop()
{
	if(isEmpty() == 0)
    	return stack[top--];
}

int main(void)
{
	int n, tmp;

	scanf("%d", &n);

	int arr[n];

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

	push(arr[0]);

	for (int i = 1; i < n; i++)
	{
    	if (stack[top] < arr[i]) 
        	push(arr[i]);
    	else if (stack[top] < arr[i])
        	continue;
    	else
    	{   
        	for (int j = top; j > -1; j--)
        	{   
            	if (arr[i] > stack[j])
                	break;

            	tmp = j;
        	}

          stack[tmp] = arr[i];
    	}

	}

	printf("%d ", top + 1);

	return 0;    
}