백준 1818 - 책정리

문제

https://www.acmicpc.net/problem/1818

풀이

최적화된 LIS 알고리즘으로 풀이할 수 있는 문제였다.

책을 정리하여 오름차순 형태로 배치해야 한다. LIS를 구하고 그 길이를 주어진 전체 책 개수에서 빼주면 이동해야할 최소의 책 개수를 구할 수 있다.

로직의 시간복잡도는 LIS 알고리즘의 $O(NlogN)$으로 수렴하므로 $N=200,000$인 최악의
경우에도 무난히 제한 조건 2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        int[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        List<Integer> lis = new ArrayList<>();
        for (int num : arr) {
            int index = Collections.binarySearch(lis, num);
            if (index < 0) index = -(index + 1);

            if (index == lis.size()) {
                lis.add(num);
            } else {
                lis.set(index, num);
            }
        }

        System.out.println(arr.length - lis.size());
        br.close();
    }
}

결과