[백준/BOJ] 백준 14003번 : 가장 긴 증가하는 부분 수열 5

www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

가장 긴 증가하는 부분 수열 O(n log n) 알고리즘 사용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
#include <cstdlib>
#include <deque>
#include <set>
using namespace std;

int n;
vector<int> input_data;
vector<int> here_finish_long(1000000); //input_data의 i번째가 마지막 숫자인 증가하는 부분수열의 가장 긴 길이 저장
vector<int> make_long;
deque<int> result;
vector<int>::iterator it;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		input_data.push_back(input);
	}

	//가장 긴 증가하는 부분 수열 O(n log n) 알고리즘 사용
	for (int i = 0; i < input_data.size(); i++)
	{
		it = lower_bound(make_long.begin(), make_long.end(), input_data[i]);

		if (it == make_long.end())
		{
			make_long.push_back(input_data[i]); //make_long에 input_data의 i번째 숫자 추가

			here_finish_long[i] = make_long.size(); //input_data의 i번째가 마지막 숫자인 증가하는 부분수열의 가장 긴 길이 저장
		}

		else
		{
			*it = input_data[i]; //make_long의 해당자리에 그 이하의 수로 업데이트

			here_finish_long[i] = it - make_long.begin() + 1; //input_data의 i번째가 마지막 숫자인 증가하는 부분수열의 가장 긴 길이 저장
		}
	}

	int find_len = make_long.size();
	for (int i = input_data.size() - 1; i >= 0; i--) //뒤에서 부터 확인해서 가장 긴 증가하는 부분 수열을 만든다
	{
		if (find_len == 0)
			break;

		if (here_finish_long[i] == find_len)
		{
			result.push_front(input_data[i]);

			find_len--;
		}
	}

	cout << result.size() << "\n";

	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << " ";
	}

	return 0;
}