가장 긴 증가하는 부분 수열 5

작성일 | In

[백준] 14003번 - 가장 긴 증가하는 부분 수열 5

문제 링크

14002번 문제와 거의 동일하나, 수열의 크기가 커서 동적 계획법의 시간복잡도 O(n2)으로는 해결할 수 없는 문제이다.
[백준] 14002번 - 가장 긴 증가하는 부분 수열 4 에서 동적 계획법 + 인덱스 추적 방법을 사용했다면, 이 문제에서는 이분 탐색 + 인덱스 추적 방법을 사용했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

vector<int> longest;
vector<int> trace;
int seq[1000001];
int n;

int main(void) {
    scanf("%d", &n);
    for(int i=0; i<n; ++i) scanf("%d", &seq[i]);

    longest.push_back(-1000000001);
    for(int i=0; i<n; ++i) {
        if(longest.back() < seq[i]) {
            longest.push_back(seq[i]);
            trace.push_back(longest.size()-2);
        }
        else if(longest.back() > seq[i]) {
            vector<int>::iterator iter = lower_bound(longest.begin(), longest.end(), seq[i]);
            *iter = seq[i];
            trace.push_back(iter-longest.begin()-1);
        }
        else
            trace.push_back(-1);
    }

    int order = -1, idx;
    for(int i=0; i<trace.size(); ++i) {
        if(order < trace[i]) {
            order = trace[i];
            idx = i;
        }
    }

    stack<int> stk;
    for(int i=idx; order >= 0 && i>=0; --i) {
        if(order == trace[i]) {
            stk.push(seq[i]);
            --order;
        }
    }
    
    printf("%d\n", longest.size() - 1);
    while(!stk.empty()) {
        printf("%d ", stk.top());
        stk.pop();
    }
}

LIS 이분 탐색 방법에서 벡터로 LIS의 길이만 정확하게 구할 수 있다고 [Algorithm] 최장 증가 부분 수열에서 다루었다.
LIS 각 원소를 정확하게 구하기 위해서 trace 배열을 추가적으로 사용한다.
trace배열은 주어진 수열 (위 코드에서 seq 배열 내 요소들) 과 1:1 대응하는 배열이다. 즉, trace[3]은 seq[3]이 LIS의 몇 번째 인덱스에 위치하는지를 의미한다.
간단한 예시를 들어 이 방법을 살펴보자.
{1,2,5,6,3}이 수열로 주어졌다고 가정한다. 이분 탐색 방법에 의해 벡터는 아래와 같이 변화할 것이다.

벡터 변화 예시

trace 배열은 해당 수열 원소가 LIS가 될 경우, LIS 내에서의 인덱스를 저장한다. trace 배열은 아래와 같이 변화할 것이다.
trace배열 변화

이분 탐색을 마치면, LIS 끝 원소의 인덱스는 trace 배열에서 가장 큰 값을 가진 요소가 된다. 이 예시에서는 원소 6이 LIS의 마지막 원소이다. 아울러 해당 trace 배열 요소값을 기준으로 역추적을 할 수 있도록 3을 order 변수에 저장한다.
trace 배열의 네 번째 인덱스부터 역순으로 탐색하며 그 값을 스택에 저장한다. 이 예시에서는 3,2,1,0이 차례로 탐색되고, 스택에는 6,5,2,1순으로 저장된다.
스택에 저장된 값을 차례로 출력하면 정답이 된다.

0%