문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 인 경우에 가장 긴 증가하는 부분 수열의 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 를 이루고 있는 가 주어진다.
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
이 문제도 LIS 길이만 묻기 때문에 lis 배열에 각 길이별 최소 끝값만 남기는 방식이 잘 맞는다. 현재 구현은 새 수가 가장 뒤보다 크면 추가하고, 그렇지 않으면 이분 탐색으로 교체할 위치를 찾아 값을 바꾼다.
핵심은 실제 부분수열을 모두 저장하지 않아도 길이 정보는 유지된다는 점이다. 끝값을 더 작은 수로 바꿔 두면 이후 원소들이 붙을 여지가 늘어나기 때문에, 배열 교체가 오히려 정답 계산에 유리하다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
System.out.println(solve(N));
}
static int solve(int N) {
int[] LIS = new int[N];
LIS[0] = arr[0];
int cnt = 1;
for (int i = 1; i < N; i++) {
if (arr[i] > LIS[cnt - 1]) {
LIS[cnt++] = arr[i];
} else {
int left = 0;
int right = cnt - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[i] > LIS[mid]) left = mid + 1;
else right = mid - 1;
}
LIS[left] = arr[i];
}
}
return cnt;
}
}복잡도
- 시간 복잡도: 각 원소를 이분 탐색으로 처리하므로 이다.
- 공간 복잡도: LIS 후보 배열을 저장하므로 이다.
마무리
이 문제도 LIS 길이만 묻기 때문에 lis 배열에 각 길이별 최소 끝값만 남기는 방식이 잘 맞는다.
