백준 2565 전깃줄 Java: 정렬 후 LIS로 최소 제거 수 구하기

백준 2565번 ‘전깃줄’은 서로 교차하지 않도록 최소 몇 개의 전깃줄을 제거해야 하는지 묻는다. A 전봇대 위치를 기준으로 정렬하면, 교차하지 않고 남길 수 있는 전깃줄은 B 위치가 strictly increasing하는 부분 수열이 된다.

• 백준 2565번 전깃줄

교차 조건을 LIS로 바꾸기

A 위치가 작은 전깃줄을 먼저 놓았다고 하자. 두 전깃줄이 교차하지 않으려면 뒤 전깃줄의 B 위치도 더 커야 한다.

A1 < A2 이고 B1 < B2  → 교차하지 않음
A1 < A2 이고 B1 > B2  → 교차함

따라서 A로 정렬한 뒤 B sequence의 LIS(Longest Increasing Subsequence)를 구하면 최대한 많이 남길 수 있는 전깃줄 수가 나온다.

최소 제거 수 = 전체 전깃줄 수 - LIS 길이

Java 코드

문제의 N ≤ 100에서는 이해하기 쉬운 O(N²) DP로 충분하다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int wireCount = Integer.parseInt(reader.readLine());
        int[][] wires = new int[wireCount][2];

        for (int index = 0; index < wireCount; index++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            wires[index][0] = Integer.parseInt(tokenizer.nextToken());
            wires[index][1] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(wires, (left, right) ->
                Integer.compare(left[0], right[0])
        );

        int[] lis = new int[wireCount];
        int longest = 0;

        for (int current = 0; current < wireCount; current++) {
            lis[current] = 1;

            for (int previous = 0; previous < current; previous++) {
                if (wires[previous][1] < wires[current][1]) {
                    lis[current] = Math.max(
                            lis[current],
                            lis[previous] + 1
                    );
                }
            }

            longest = Math.max(longest, lis[current]);
        }

        System.out.println(wireCount - longest);
    }
}

left[0] - right[0] 대신 Integer.compare()를 사용해 comparator overflow 가능성을 없앴다. 문제에서는 A와 B의 같은 위치에 두 전깃줄이 연결되지 않는다고 보장하므로 tie-breaker가 필요하지 않다.

교차 횟수가 많은 줄부터 지우면 왜 실패하나

원문 첫 시도는 각 전깃줄의 현재 교차 횟수를 세고 가장 많이 교차하는 줄부터 제거하는 greedy였다. 9%에서 틀렸다. 한 줄을 제거하면 다른 줄들의 교차 관계가 함께 변하고, 지금 가장 많이 교차하는 줄을 지우는 선택이 최종 제거 수를 최소화한다는 보장이 없기 때문이다.

LIS는 “어떤 줄을 먼저 지울까”가 아니라 교차하지 않는 최대 집합을 한 번에 찾는다. 제거 문제를 보존 문제로 뒤집은 셈이다.

세 시간 걸린 LIS가 다음 문제에서 보였다

원문에는 문제를 다시 읽고 A로 정렬하자 백준 11053 LIS로 변한다는 점을 발견했다고 적혀 있다. 익명 comparator와 lambda 두 version도 비교했다.

당시 lambda version의 메모리와 시간이 한 번의 제출에서 더 크게 나왔다고 기록했지만, online judge의 단일 측정만으로 lambda 자체가 느리다고 결론낼 수는 없다. class loading, JVM 상태와 측정 변동을 통제한 benchmark가 아니기 때문이다. 여기서는 표현이 짧은 lambda를 쓰되 안전한 comparison method를 사용했다.

Java comparator의 계약은 compareTo와 Comparator 정리, O(N log N) LIS는 백준 12015 풀이에서 이어서 볼 수 있다.

복잡도와 검증 범위

정렬은 O(N log N), LIS DP는 O(N²), 공간은 O(N)이다. Java source를 수동 검토하고 이미 교차하지 않는 경우, 모두 역순인 경우와 작은 random matching을 모든 subset의 non-crossing 여부와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.