무지개 달팽이

Q. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력.

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력.

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

11053 번과 유사한 문제이다. 그래서 같은 코드를 제출하였더니, 시간 초과가 났다.

해결하기 위해 LIS 알고리즘에 대해 구글링해 본 결과, 수열의 크기가 전의 문제보다 더 크다는 점이 문제점이라는 것을 알아 냈다.

( ※ 참고 블로그 : https://jason9319.tistory.com/113 )

위 블로그를 통해 공부한 결과는 아래와 같다.

이 문제는 LIS 알고리즘을 이분 탐색의 방향으로 봐야 한다.

우선 특정 수열의 값을 정렬할 배열을 새로 하나를 만들어 주어야 한다.  위 블로그에서는 벡터를 이용하였는데, c언어를 사용하기 위해 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;    
}