[백준 14003] 가장 긴 증가하는 부분 수열 5 / 자바 / LIS

#문제         

레벨: P5
알고리즘: LIS(이분탐색)
풀이시간: 40분
힌트 참조 유무:

https://www.acmicpc.net/problem/14003

 

---

#문제 풀이        

지난 LIS 문제들은 길이를 구하라고 하면 시간복잡도가 빡빡해서  이분탐색으로 풀어야 했고 LIS를 출력하라고 하면 시간복잡도가 넉넉했다. 그 이유는 이분탐색으로 LIS를 구하면 O(n)으로 구할 수는 있지만 LIS가 정확하지 않을 수 있기 때문이다. 

그 예로는 아래 배열을을 참고해보자

2 6 3 4 1 5

1. [2]
2. [2, 6]
3. [2, 3] (6을 3으로 대체)
4. [2, 3, 4]
5. [1, 3, 4] (2를 1로 대체)
6. [1, 3, 4, 5]

최종적으로 얻은 배열 [1, 3, 4, 5]는 실제 LIS가 아니다. 1은 원래 수열의 맨 뒤쪽에 있어서 실제 LIS의 일부가 될 수 없다. 이 방법은 LIS의 길이(4)는 정확하게 구할 수 있지만, 실제 LIS 자체는 정확하게 구하지 못한다.

 

그런데 이 문제는 시간복잡도도 빡빡하지만, 실제 LIS를 구해야 한다. 그래서 우리는 L배열은 이분탐색의 길이를 위해 평소와 같이 요소를 넣을 거고 P에서는 실제 LIS를 출력하기 위해  LIS의 순위를 적어 놓을 것이다.

---

#풀이 코드      

import java.util.*;
import java.io.*;

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());
        int[] A = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int[] L = new int[n];
        int[] P = new int[n];
        int len = 0;

        for (int i = 0; i < n; i++) {
            int pos = Arrays.binarySearch(L, 0, len, A[i]);
            if (pos < 0) pos = -(pos + 1);
            L[pos] = A[i];
            P[i] = pos;
            if (pos == len) len++;
        }

        System.out.println(len);

        int[] result = new int[len];
        int k = len - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (P[i] == k) {
                result[k] = A[i];
                k--;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

---

#비슷한 유형      

https://jsw5913.tistory.com/123

[백준] 가장 긴 증가하는 부분 수열 2 / 자바 **