🙇‍♀️[Platinum V] 가장 긴 증가하는 부분 수열 5 - 14003

문제 링크

성능 요약

메모리: 18216 KB, 시간: 212 ms

분류

이분 탐색, 가장 긴 증가하는 부분 수열: O(n log n)

제출 일자

2024년 2월 27일 13:00:29

문제 설명

수열 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,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

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

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

🚀풀이

가장 긴 증가하는 부분 수열 4와 마찬가지로 dp를 이용해서 풀려고 했다.

음수는 판별할 수 없는 코드가 가중치를 줘서 모두 양수로 만들고 풀면 될 줄 알았는데 n이 높아져서 시간초과가 났다.

이분탐색으로 풀어야하는 문제인데 잘 몰라서 다른 사람 코드 보고 풀었다.

int n;
int arr[1000010];
int indexArr[1000010];
vector<int> v;

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= n; ++i)
	{
        // 비었으면 무조건 넣긴해야 됨
        // 그 뒤 조건은 증가 수열인지 확인하는 것.
		if (v.size() == 0 || v[v.size() - 1] < arr[i])
		{
			v.push_back(arr[i]);
			indexArr[i] = v.size() - 1;
		}
		else
		{
            // 여기로 온건 v끝값보다 작은 경우
            // 여기서 최소값을 찾는다?
            // 키 값이 arr[i]이다
            // arr[i]위치를 배정한다
			int left = 0;
			int right = v.size() - 1;
			while (left < right)
			{
				int mid = (left + right) / 2;

				if (v[mid] >= arr[i])
					right = mid;
				else
					left = mid + 1;
			}
			v[left] = arr[i];
			indexArr[i] = left;
		}
	}

    // 여기까지 오면 인덱스와 v의 수열이 채워진 상태
	cout << v.size() << '\n';

    // 인덱스를 바탕으로 역추적 시작
	stack<int> ans;
	int idx = v.size() - 1;
	for (int i = n; i > 0; --i)
	{
		if (indexArr[i] == idx)
		{
			idx--;
			ans.push(arr[i]);
		}
	}

	while (ans.empty() == false)
	{
		cout << ans.top() << " ";
		ans.pop();
	}
}

image

플레 문제 아직 풀지말걸.. 골드 4,5나 풀어야겠다..

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int n;
int arr[1000010];
int indexArr[1000010];
vector<int> v;

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= n; ++i)
	{
		if (v.size() == 0 || v[v.size() - 1] < arr[i])
		{
			v.push_back(arr[i]);
			indexArr[i] = v.size() - 1;
		}
		else
		{
			int left = 0;
			int right = v.size() - 1;
			while (left < right)
			{
				int mid = (left + right) / 2;

				if (v[mid] >= arr[i])
					right = mid;
				else
					left = mid + 1;
			}
			v[left] = arr[i];
			indexArr[i] = left;
		}
	}

	cout << v.size() << '\n';

	stack<int> ans;
	int idx = v.size() - 1;
	for (int i = n; i > 0; --i)
	{
		if (indexArr[i] == idx)
		{
			idx--;
			ans.push(arr[i]);
		}
	}

	while (ans.empty() == false)
	{
		cout << ans.top() << " ";
		ans.pop();
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고