가장 긴 증가하는 부분 수열 1 문제는 n
의 범위가 작아서 DP로 풀 수 있었지만, 이번 문제는 n
의 범위가 100만까지 늘어났기 때문에 DP로는 풀 수 없다. 따라서 이분 탐색으로 문제에 접근해야 한다.
전체적인 풀이는, List의 적절한 위치에 원소들을 삽입해가는 방식으로 이루어진다. 주어진 arr
의 원소들을 한 번씩 탐색하고, 각 원소마다 List에서 적절한 위치를 이분 탐색으로 찾는 것으로, 총 O(NlogN)
의 시간복잡도로 해결 가능하다.
또한, LIS 전체를 구하는 것이 아니라 길이만 구하면 되기 때문에 하나의 List만 활용해서 O(N)
의 공간복잡도로 문제 해결이 가능하다.
원소 arr[i]
를 삽입하는 방법은 두 가지 경우로 나뉘어진다.
lis
의 마지막 원소보다 큰 경우:lis
의 마지막에add()
lis
의 마지막 원소 이하인 경우:lis
에서arr[i]
이상 값 중 최솟값의 index를 찾아서set(index, arr[i])
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Main {
private static int n;
private static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
parseInput(br);
int answer = findLISLength();
bw.append(String.valueOf(answer));
br.close();
bw.close();
}
private static void parseInput(BufferedReader br) throws IOException {
n = Integer.parseInt(br.readLine());
arr = new int[n];
String[] line = br.readLine().split(" ");
for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(line[i]);
}
private static int findLISLength() {
List<Integer> lis = new ArrayList<>();
lis.add(0);
for (int i = 0; i < n; i++)
if (arr[i] > lis.get(lis.size() - 1)) lis.add(arr[i]);
else lis.set(findIndex(lis, arr[i]), arr[i]);
return lis.size() - 1;
}
private static int findIndex(List<Integer> lis, int current) {
int left = 0, right = lis.size() - 1, mid;
while (left < right) {
mid = (left + right) / 2;
if (current > lis.get(mid)) left = mid + 1;
else right = mid;
}
return (left + right) / 2;
}
}
[백준 11053 / 백준 12015] 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence) - 1
[백준 12015 : JAVA] 가장 긴 증가하는 부분 수열 2 / 이진탐색 풀이