[BOJ] 백준 14003 가장 긴 증가하는 부분 수열 5 (Swift)

문제

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

14003번: 가장 긴 증가하는 부분 수열 5

풀이

N이 100만이므로 LIS를 $O(nlogn)$의 시간복잡도로 구하는 방식으로 풀이해야합니다.
이전 포스팅에서 길이를 구하였는데, 수열은 어떠한 방식으로 구할 수 있을까요?
https://dev-mandos.tistory.com/245

[BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 (Swift)

수열이 추가되거나 이진탐색으로 교체를 할 때, 해당 index를 담을 배열을 만들어주어야 합니다.

[10, 20, 10, 30, 10, 40] 라는 배열이 있다면, LIS는 [10, 20, 30, 40] 이고, 길이는 4입니다.

하나씩 확인을 해보면,

1. LIS = [1], index = [0]
2. LIS = [10, 20], index = [0, 1]
3. LIS = [10, 20] (10이 10과 교체), index = [0, 1, 0] (기존 10의 위치가 0이므로)
4. LIS = [10, 20, 30], index = [0, 1, 0, 2]
5. LIS = [10, 20, 30], index = [0, 1, 0, 2, 0]
6. LIS = [10, 20, 30, 40], index = [0, 1, 0, 2, 0, 3]

이제 이 index배열을 뒤에서 부터 3 -> 2 -> 1 -> 0 순으로 조회하면, 기존 배열의 인덱스에 해당하는 요소가 LIS를 이루게 됩니다.
역순으로 조회하였기 때문에 역순으로 출력해주면 됩니다.

소스코드

후기

14002 가장 긴 증가하는 부분 수열 4 문제와 비슷했지만, 시간복잡도가 덜 드는 방법으로 풀어야했습니다.