[알고리즘] 백준 > #3745. 오름세

문제링크

백준 #3745. 오름세

풀이방법

문제를 읽고 백준 > #12015. 가장 긴 증가하는 부분 수열 2 이 문제가 생각났다. 풀이방법이 동일하다. LIS를 사용했다. price를 오름차순으로 sort(price가 같다면 index를 내림차순으로)하고 그 순서대로 tree에 반영하는데, 그 인덱스(i) 앞에 최대값 + 1을 해준다. 이는 i 원소를 마지막 원소로 하는 가장 긴 증가하는 부분 수열의 길이를 의미한다. 인덱스 값이 추가되기 때문에 + 1을 해준다. i 앞 최대값 또한 세그먼트트리를 이용한다(getMaxCount 메소드). 만약 다른 리스트에 그 count 값을 저장하고 for문을 돌리면 시간초과가 난다! #12015와 비슷한 문제라 설명은 여기서 끝!

코드

class Solution3745 {

    private int n;
    private int[] stocks;

    int[] tree;

    Solution3745(int n, int[] stocks) {
        this.n = n;
        this.stocks = stocks;
    }

    int getLongestIncreasePeriod() {
        Stock[] stockWithIndex = new Stock[n];
        for (int i = 0; i < n; i++) stockWithIndex[i] = new Stock(i, stocks[i]);
        Arrays.sort(stockWithIndex);

        tree = new int[n * 4];

        for (int i = 0; i < n; i++) {
            fillTree(1, getMaxCount(0, stockWithIndex[i].index - 1, 1, 0, n - 1) + 1, 0, n - 1, stockWithIndex[i].index);
        }

        return tree[1];
    }

    private int fillTree(int index, int value, int startRange, int endRange, int target) {
        if (startRange == endRange) return tree[index] = value;
        else {
            int mid = (startRange + endRange) / 2;

            if (startRange <= target && target <= mid) tree[index] = Math.max(tree[index], fillTree(index * 2, value, startRange, mid, target));
            else tree[index] = Math.max(tree[index], fillTree(index * 2 + 1, value, mid + 1, endRange, target));

            return tree[index];
        }
    }

    private int getMaxCount(int l, int r, int index, int nodeL, int nodeR) {
        if ((l > nodeR) || (r < nodeL)) return 0;
        else if ((l <= nodeL) && (r >= nodeR)) return tree[index];

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

class Stock implements Comparable<Stock> {
    int index;
    int price;

    Stock(int index, int price) {
        this.index = index;
        this.price = price;
    }

    @Override
    public int compareTo(Stock o) {
        if (this.price == o.price) return o.index - this.index;
        else return this.price - o.price;
    }
}