백준 26481: 수열과 쿼리 42, 시간 초과가 난 LIS 풀이

백준 26481번 ‘수열과 쿼리 42’를 풀다가 시간 초과가 났습니다. 아직 해결하지 못한 코드이므로 정답 풀이로 참고하면 안 됩니다.

쿼리마다 LIS를 다시 구합니다

각 쿼리의 양 끝 l, r을 0부터 시작하는 인덱스로 바꾸고 그 구간의 최장 증가 부분 수열(LIS) 길이를 계산합니다.

lis에는 길이별로 증가 부분 수열의 마지막 값 후보를 저장합니다. 새 값이 현재 마지막 값보다 크면 길이를 늘립니다. 그렇지 않으면 이분 탐색으로 새 값 이상인 첫 위치를 찾아 교체합니다. lis 배열 전체가 실제 부분 수열을 나타내는 것은 아닙니다.

쿼리가 올 때마다 새 배열을 만들어 해당 구간을 처음부터 끝까지 다시 확인합니다. 구간 길이를 L이라 하면 쿼리 하나에 O(L log L)이 듭니다. 모든 쿼리가 전체 수열을 다루는 경우에는 O(QN log N)의 계산이 필요합니다. 둘 다 실제 실행 시간을 측정하지 않고 코드 구조만 보고 따진 비용입니다.

시간 초과가 난 코드

Java

import java.io.*;
import java.util.*;

class Main {

    static int N,Q;
    static int l,r;
    static int[] arr;
    static int[] lis;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            l = Integer.parseInt(st.nextToken())-1;
            r = Integer.parseInt(st.nextToken())-1;
            int longest = longest();
            bw.write(String.valueOf(longest));
            bw.write("\n");
        }
        bw.flush();
    }

    public static int longest() throws IOException {
        lis = new int[r-l+1];
        int j = 0;
        if ((r - l + 1) == N) {
            lis[0] = arr[0];
        } else {
            lis[0] = arr[l];
        }
        for(int i =l ; i < r+1; i++) {
            if (lis[j] < arr[i]) {
                lis[j + 1] = arr[i];
                j += 1;
            }
            else {
                int idx = binarySearch(0, j, arr[i]);
                lis[idx] = arr[i];
            }
        }

        return j + 1;

    }
    public static int binarySearch(int left, int right, int target) {

        int mid;

        while (left < right) {
            mid = (left + right) / 2;

            if (lis[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return right;
    }
}