[백준 c++] 12015 가장 긴 증가하는 부분 수열 2

문제

https://www.acmicpc.net/problem/12015
LIS의 길이를 구하는 문제

풀이

이전에 풀었던 LIS 문제들은 입력 수열의 크기가 (1 ≤ N ≤ 1,000)이지만
이 문제는 (1 ≤ N ≤ 1,000,000) 때문에 기존 O(N^2) 소요되는 풀이로는 풀 수 없다.

lower_bound를 이용한 각 원소들의 최적의 위치를 찾는 방식으로 LIS길이를 O(NlogN)에 구했다.

입력배열 int num[]
원소들의 최적 위치 찾는 벡터 vector v

0. num 배열 순회
   A. v가 비어있으면 v.push(num[i])
   B-1. v의 마지막 값보다 num[i]가 크면 v.push(num[i])
   B-2. 아니라면 num[i]가 들어갈 위치의 값을 num[i]로 바꿔준다*lower_bound(v.begin(),v.end(),num[i]) = num[i]

🚨 주의할 점

이 방법은 LIS 길이를 구할 때만 쓸 수 있다.
vector v는 LIS의 길이만 나타낼 뿐 요소를 포함하는 배열이 아니다!
입력 배열이{8, 9, 10}일 때 위 과정대로 하면 v는 {8, 10}이 된다.
`

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, num[1000001];
vector<int> v;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    for (int i = 0; i < n; i++)
    {
        if (v.empty())
            v.push_back(num[i]);
        else
        {
            if (v[v.size() - 1] < num[i])
                v.push_back(num[i]);
            else
                *lower_bound(v.begin(), v.end(), num[i]) = num[i];
        }
    }
    cout << v.size() << "\n";
    return 0;
}