오랜만에 P5 푼 기념
풀이 과정 🔎
우선 주어지는 수열의 크기가 1,000,000이기 때문에 O(n^2)로는 안 된다는 건 금방 알 수 있다. 부분 수열 문제 자체도 좀 오랜만이긴 했지만 기억을 더듬어... O(n log n)으로 최장 증가 부분 수열의 길이를 구할 수 있는 알고리즘을 떠올렸다.
배열
len을 정의해len[i]가 증가 부분 수열의 i번째 원소가 될 수 있는 최솟값을 갖도록 한다. 즉 새로운 원소k가 주어졌을 때,
- 배열이 비어 있거나 배열에 들어 있는 최댓값보다 클 경우 배열의 맨 뒤에 원소를 넣는다.
- 현재 배열에 들어 있는 최솟값보다 작거나 같을 경우
len[0]을 수정한다.- 두 경우 다 아니라면 이분탐색을 통해
len에서k이상인 최솟값을 찾고, 그 값을k로 수정한다.
위 방식을 사용했을 때 len의 길이가 최장 증가 부분 수열의 길이이다. 다만 위 알고리즘으로는 최장 증가 부분 수열을 구할 수는 없다.
따라서 위의 과정에 더해 증가 부분 수열에서 해당 원소의 바로 앞에 있는 원소를 찾고자 했다. 위 알고리즘을 통해 주어진 배열에서 k보다 앞에 있으면서, k보다 작은 최댓값을 찾을 수 있다. 이 값을 또 다른 배열 back을 통해 관리하면 len 배열의 최댓값에서 시작해서 수열을 거슬러 올라가는 방식으로 전체 최장 증가 부분 수열을 찾을 수 있다.
