14003번 - 가장 긴 증가하는 부분 수열 5
1️⃣ LIS 알고리즘, 이분 탐색
✏️ 풀이 과정
이전의 가장 긴 증가하는 부분 수열 2 문제에서 추가적으로 LIS의 내용을 같이 출력하라는 문제입니다. 이 문제를 어렵게 만드는 것은, 이분 탐색을 사용하는 방법에서는 앞부분에 더 낮은 수가 발견되면 업데이트시켜서 나중에 더 긴 수열이 발견하는 것을 의도하기 때문에 LIS의 내용이 실제와 차이가 있다는 부분입니다.
이분탐색을 사용하지 않는 방법(O(N^2))을 사용했다면 수열을 업데이트할 때 어떤 인덱스를 끝으로 하는 수열을 기준으로 하기 때문에 마지막 인덱스 이전이 어느 인덱스인지를 바로 얻을 수 있습니다. 하지만 이분탐색의 경우에는 기존에 사용하던 식에 이러한 정보가 없기 때문에 추가적인 작업이 필요합니다.
기본적인 아이디어는 중간 부분이 업데이트되어도 이전까지의 정보는 여전히 유효하다는 것입니다. 가령 1 3 6 7 9라는 수열에서 1 3 5 7 9로 업데이트되었다 하면 LIS의 내용은 1 3 6 7 9이지만 새로운 수열이 될 가능성이 있는 1 3 5에서 앞부분의 1 3은 업데이트가 되어도 여전히 유효합니다.
이러한 점을 이용해서 어떤 지점을 업데이트할 때마다 그 지점의 바로 앞 수가 어느 인덱스인지를 저장하면 계속 앞으로 추적해가면서 가장 긴 LIS의 마지막 수로부터 처음까지 수열의 내용을 복원해낼 수 있습니다.
이를 위해서는 두 배열이 필요한데 한 가지는 LIS배열의 특정 인덱스가 arr의 어느 인덱스에서 왔는지 저장하는 trace 배열이고 나머지 하나는 LIS가 arr의 i 인덱스로 업데이트될 때 LIS의 교체 지점 바로 직전에 어떤 수가 있었는지(arr에서의 인덱스로 저장) 저장하는 prev 배열입니다.
두 배열을 이용하면 LIS의 max 값을 구했을 때 trace의 마지막 원소 혹은 LIS의 마지막 원소로부터 시작해서 이전 인덱스를 저장해놓은 prev 배열을 계속 타고 올라가면서 수열의 내용을 복원해낼 수 있습니다. 이 과정은 역순이기 때문에 배열을 새로 만들고 max-1인덱스부터 채워넣은 다음 StringBuilder로 출력할 내용을 새로 만들어내는 것이 빠릅니다.(처음부터 StringBuilder의 insert 기능을 이용하면 insert의 오버헤드가 굉장히 큰 편이기 때문에 시간 내에 문제를 해결하지 못하거나 시간이 원래보다 훨씬 많이 소요됩니다.)
⏱ 시간 복잡도
추가적으로 저장 로직이 들어갔을 뿐 LIS를 찾는 로직 자체는 동일하기 때문에 이진 탐색을 N번 행하는 이 알고리즘의 시간 복잡도는 O(NlogN)이 됩니다. 수열의 크기가 최대 1,000,000이기 때문에 O(N^2)으로는 문제를 해결할 수 없어 반드시 이분 탐색을 사용해야 합니다.
💻 코드
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
int[] LIS = new int[N];
int[] trace = new int[N];
int[] prev = new int[N];
int max = 0;
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
int pos = Arrays.binarySearch(LIS, 0, max, arr[i]);
if(pos < 0) {
pos = -1 * (pos + 1);
LIS[pos] = arr[i];
trace[pos] = i;
if(pos != 0) {
prev[i] = trace[pos - 1];
}
if(pos == max) {
max++;
}
}
}
sb.append(max+"\n");
int[] result = new int[max];
for(int i=max-1, j=trace[max-1];i>=0;i--) {
result[i] = arr[j];
j = prev[j];
}
for(int i : result) {
sb.append(i + " ");
}
System.out.print(sb);
br.close();
}
}