백준 1365 - 꼬인 전깃줄

문제

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

풀이

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

주어진 전봇대에서 전선이 꼬이지 않으려면 결국, 전봇대의 순서가 오름차순이 되어야 한다.
따라서 LIS의 길이를 구해 주어진 전체 전봇대 개수에서 빼주면 제거해야 하는 최소 전선의
개수가 된다. 최적화된 LIS 알고리즘에 대한 설명은 여기를 참고하자.

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

코드

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();
    }
}

결과