[14003] 가장 긴 증가하는 부분 수열 5

분류 : 이분 탐색
시간복잡도 : O(nlogn)

 

 

https://qhdks.tistory.com/134

[12015] 가장 긴 증가하는 부분 수열 2

 

위 문제의 풀이 방식에서 경로 추적 코드를 넣어주면 된다.

 

경로 추적은 어떻게 할까?

보통은 way[10]이 있을 때, 1-3-4-2-5-8-7-9-6 의 순서를 가진다면,

i	1	2	3	4	5	6	7	8	9
way	-1	4	1	3	2	9	8	5	7

과 같이 이전 위치를 저장한다.

이를 이용해서 해결하면 된다.

 

가장 긴 증가하는 부분 수열 2 문제 풀이에서 구한 dp의 값은 길이에 따른 가장 작은 마지막 값을 저장한 것이므로 경로가 될 수 없다.

이때, dp가 갱신되는 과정을 자세히 살펴보면, 갱신되는 순간에 새로 들어온 숫자부터 배열의 첫번째 원소까지가 해당 길이의 경로이다. 하지만, 이는 다시 새로 갱신되면 사라지기 때문에, 배열에 최솟값을 갱신할 때 경로도 갱신하면 된다.

 

다음 예시를 보자.

현재 상태는 i = 2를 탐색중이며, dp[1]의 값을 갱신하고자 한다. dp[1] 값에 대한 경로는 인덱스 0으로 부터 왔으며, 최솟값이다.

i	0	1	2	3	4	5
arr	10	20	15	30	25	50
dp	10	20
way	-1	0	-1	-1	-1	-1

 

i	0	1	2	3	4	5
arr	10	20	15	30	25	50
dp	10	15
way	-1	0	0	-1	-1	-1

현재 길이 2의 부분 수열은 2개가 있으며, way를 통해 확인하면 {10, 20}, {10, 15}가 있음을 확인할 수 있다.

따라서, 이를 마지막까지 수행하면 경로를 얻어낼 수 있다.

 

이때, 출력은 첫 번째 원소부터 해야하므로 스택에 한 번 집어넣었다가 다시 빼면서 출력하는 방법을 선택했다.