초보개발자

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

카테고리 없음

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

___yejin 2017. 7. 6. 12:47
  • 입력: 수열의 크기N(1 ≤ N ≤ 1,000,000), 수열을 나타내는 정수 Ai (1 ≤ Ai ≤ 1,000,000)
  • 출력: 가장 긴 증가하는 부분 수열의 길이를 출력
  • 실패한 소스코드
    • ?
    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
    50
    51
    52
    53
    54
    55
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
     
    int max(vector<int>, int, int, int, int, int);
    void update(vector<int>&, int, int, int, int, int);
     
    int main() {
        int N;
        scanf("%d", &N);
        vector<pair<int, int> > arr(N);
        for (int i = 0; i < N; i++) {
            scanf("%d", &arr[i].first);
            arr[i].second = i;
        }
     
        sort(arr.begin(), arr.end());
     
        int h = (int)ceil(log2(N));
        vector<int> tree(1 << (h + 1), 0);
     
        int maxLength;
        for (int i = 0; i < N; i++) {
            maxLength = max(tree, 1, 0, arr[i].second, 0, N - 1);
            if (i != 0 && arr[i - 1].first == arr[i].first) update(tree, 1, 0, N - 1, arr[i].second, maxLength);
            else update(tree, 1, 0, N - 1, arr[i].second, maxLength + 1);
        }
     
        printf("%d\n", tree[1]);
     
     
        return 0;
    }
     
    int max(vector<int> tree, int node, int left, int right, int start, int end) {
        if (left > end || right < start) return 0;
        if (left <= start && end <= right) return tree[node];
     
        int a = max(tree, node * 2, left, right, start, (start + end) / 2);
        int b = max(tree, node * 2, left, right, (start + end) / 2 + 1, end);
        return (a > b ? a : b);
    }
     
    void update(vector<int>& tree, int node, int start, int end, int index, int key) {
        if (index < start || index > end) return;
        tree[node] = (tree[node] > key ? tree[node] : key);
     
        if (start != end) {
            update(tree, node * 2, start, (start + end) / 2, index, key);
            update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, key);
        }
    }
    세그먼트 트리를 이용하여 구현하였지만 시간초과가 났다. 트리에 가장 긴 부분수열의 길이를 기록한다.
  • 성공한 소스코드
    • ?
    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
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
     
     
    int main() {
        int N;
        scanf("%d", &N);
        vector<int> arr(N);
        for (int i = 0; i < N; i++)
            scanf("%d", &arr[i]);
     
        vector<int> lis;
        lis.push_back(-1);
        for (int i = 0; i < N; i++) {
            if (lis.back() < arr[i]) {
                lis.push_back(arr[i]);
            }
            else {
                auto it = lower_bound(lis.begin(), lis.end(), arr[i]);
                *it = arr[i];
            }
        }
     
        printf("%d\n", lis.size() - 1);
     
        return 0;
    }
    세그먼트 트리가 아닌, 그냥 vector를 이용하여 구현하였다. lower_bound 함수를 사용했기 때문에 O(NlogN)일 것이라고 추정된다.


저작자표시
공유하기 링크
'전체' Related Articles more
Comments