[알고리즘] 백준 > #12015. 가장 긴 증가하는 부분 수열 2

와 굉장히 어려웠다

문제링크

백준 #12015. 가장 긴 증가하는 부분 수열 2

풀이방법

어려운 문제였다. 세그먼트 트리를 사용해 문제를 해결했는데, 세그먼트트리를 사용해야한다고 생각하는 과정도 어려웠고 시간초과가 나서 그걸 해결하는것도 힘들었다 -0-

일단, 세그먼트트리 아이디어를 얻은 과정은 다음과 같다. 이 문제는 dp로도 풀 수 있는 문제인데, dp로 풀었을 때 dp[i]의 의미는 i원소를 마지막 원소로 하는 가장 긴 증가하는 부분 수열의 길이를 의미한다. 이 의미를 갖는 값을 dp가 아니라 어떻게 효과적으로 구할까 생각했다. 배열 a에 대해서 오름차순으로 접근하자고 생각했다. 그러자 세그먼트트리를 구간최대값을 구하는데 사용하면 효과적일거 같았다 !!!!! 즉, a 값에 대해서 오름차순으로 세그먼트트리를 업데이트 하는 방식인데 이렇게 업데이트를 진행하면 이미 진행된 값들이 현재 진행되는 값보다 작은 값을 가지기 때문에 [0, index) (index는 현재 진행되는 a의 인덱스를 의미한다) 범위 내 가장 큰 값에 + 1을 해주면된다. 이 범위 내 가장 큰 값도 세그먼트트리를 활용하면 간단히 구할 수 있다! 근데 이 문제에서는 중복된 값이 주어질 수 있기 때문에 배열 a 정렬 시 값이 같다면 index를 비교해 내림차순으로 정렬해줘야한다.

그리고 시간초과가 났다. 뭐가 이유인지 몰라서 모든 재귀함수를 for문을 이용한 반복문으로 바꿨다.. 근데 Scanner가 문제였다. Scanner를 다른 방식으로 바꾸니 시간초과가 해결됐다!

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.io.IOException;
public class BOJ12015 {

    static private int[] a;
    static int startIndex;
    static int[] tree;

    static private ElementInfo[] elementInfos;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());

        a = new int[n];
        elementInfos = new ElementInfo[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
            elementInfos[i] = new ElementInfo(a[i], i);
        }
        Arrays.sort(elementInfos);

        for (startIndex = 1; startIndex < n; startIndex *= 2) ;
        tree = new int[startIndex * 2 - 1 + 1];

        for (int i = 0; i < n; i++) {
            int index = elementInfos[i].index;
            updateTree(startIndex + index, findMaxLISLength(0, index, 1, 0, startIndex - 1) + 1);
        }

        System.out.print(tree[1]);
    }

    static void updateTree(int index, int value) {
        while (index != 0) {
            tree[index] = value;

            int parentIndex = index / 2;
            if (tree[parentIndex] < value) index = parentIndex;
            else index = 0;
        }
    }

    static int findMaxLISLength(int l, int r, int nodeIndex, int nodeL, int nodeR) {
        if ((l > nodeR) || (r < nodeL)) return 0;
        else if ((l <= nodeL) && (r >= nodeR)) return tree[nodeIndex];

        int mid = (nodeL + nodeR) / 2;
        int leftChildValue = findMaxLISLength(l, r, nodeIndex * 2, nodeL, mid);
        int rightChildValue = findMaxLISLength(l, r, nodeIndex * 2 + 1, mid + 1, nodeR);
        return leftChildValue > rightChildValue ? leftChildValue : rightChildValue;
    }
}

class ElementInfo implements Comparable<ElementInfo> {
    public int value;
    public int index;

    public ElementInfo(int value, int index) {
        this.value = value;
        this.index = index;
    }

    @Override
    public int compareTo(ElementInfo o) {
        if (this.value != o.value) return this.value - o.value;
        else return o.index - this.index;
    }
}