[BOJ/Java] 2565. 전깃줄

[BOJ/Java] 2565. 전깃줄

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

---

문제 해석

문제는 주어진 전깃줄이 교차하지 않도록 최소 몇 개의 전깃줄을 제거해야 하는지를 묻고 있다. 이 문제는 동적 계획법을 이용한 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제의 변형으로 볼 수 있다. A와 B 두 전봇대에 연결된 전깃줄의 위치가 주어지며, 각 전깃줄은 A전봇대의 특정 위치에서 B전봇대의 특정 위치로 연결된다.

풀이 과정

주어진 입력으로부터 전깃줄 정보를 배열에 저장하고, A 전봇대에 대해 오름차순 정렬을 실시한다. 이후, B 전봇대의 위치를 기준으로 LIS를 계산하여, 교차하지 않는 최대 전깃줄 수를 찾는다. LIS의 길이가 교차하지 않는 최대 전깃줄의 수를 의미하며, 전체 전깃줄 수에서 LIS 길이를 빼면, 제거해야 할 최소 전깃줄 수를 구할 수 있다.

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N;  // 전깃줄의 총 개수
    private static Line[] lines;  // 전깃줄 정보를 저장할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());  // 전깃줄의 개수를 입력 받음
        lines = new Line[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            lines[i] = new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        sb.append(sol());  // 결과를 StringBuilder에 추가
        bw.write(sb.toString());  // 결과를 출력
        bw.flush();
        bw.close();
    }
    
    private static int sol() {
        int[] length = new int[N];  // 각 위치에서의 최장 증가 부분 수열 길이를 저장할 배열

        Arrays.sort(lines);  // 전깃줄을 A 위치 기준으로 정렬
        for (int k = 0; k < N; k++) {
            length[k] = 1;  // 최소 한 개의 전깃줄은 존재
            for (int i = 0; i < k; i++) {
                if (lines[i].b < lines[k].b) length[k] = Math.max(length[k], length[i] + 1);  // LIS 계산 로직
            }
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            ans = Math.max(ans, length[i]);  // 최장 증가 부분 수열의 최대 길이를 찾음
        }

        return N - ans;  // 전체 개수에서 최장 길이를 빼 제거해야 할 전깃줄 수 계산
    }

    static class Line implements Comparable<Line> {
        int a, b;  // 전봇대 A, B 위치

        public Line(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public int compareTo(Line o) {
            return a - o.a;  // A 위치 기준으로 정렬
        }
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도는 전깃줄 배열을 정렬하는 데 𝑂(𝑁log⁡𝑁)이 소요되며, 각 전깃줄에 대해 이전 전깃줄들과 비교하여 LIS를 계산하는 데 𝑂(𝑁^2)의 시간이 필요하다. 따라서 전체적인 시간 복잡도는 𝑂(𝑁^2)이다.

느낀점

이 문제를 통해 교차 문제를 LIS를 활용해 해결하는 방법을 배울 수 있었다. 또한, 각 알고리즘의 시간 복잡도에 따라 입력 사이즈가 커졌을 때의 성능 영향도 파악할 수 있었다.