전부 포함하는 선분

문제 개요

1차원 좌표 위에 여러 개의 선분이 주어진다. 이 중 하나를 제거했을 때, 나머지 선분들을 전부 포함할 수 있는 최소 길이의 선분을 구하는 문제이다.
선분은 x좌표의 시작점과 끝점 (x1, x2)로 주어지며, 조건을 만족하는 가장 짧은 선분 길이를 출력해야 한다.

---

브루트 포스 방식

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x1 = new int[n];
        int[] x2 = new int[n];
        for (int i = 0; i < n; i++) {
            x1[i] = sc.nextInt();
            x2[i] = sc.nextInt();
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;

                max = Math.max(max, x2[j]);
                min = Math.min(min, x1[j]);
            }

            ans = Math.min(ans, max - min);
        }

        System.out.println(ans);
    }
}

특징

• 각 선분을 하나씩 제외하고 남은 선분들의 전체 포함 범위를 계산함
• 시간 복잡도: O(n^2)

---

최적화 방식

import java.util.Scanner;

public class Main {
    public static final int INT_MAX = Integer.MAX_VALUE;
    public static final int MAX_N = 100;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x1 = new int[MAX_N];
        int[] x2 = new int[MAX_N];
        int ans = INT_MAX;

        for(int i = 0; i < n; i++) {
            x1[i] = sc.nextInt();
            x2[i] = sc.nextInt();
        }

        // 시작점이 가장 작은 선분 제거
        int skip = 0;
        for(int i = 0; i < n; i++) {
            if(x1[skip] > x1[i]) skip = i;
        }

        int max_x2 = 0;
        int min_x1 = INT_MAX;
        for(int i = 0; i < n; i++) {
            if(i == skip) continue;
            max_x2 = Math.max(max_x2, x2[i]);
            min_x1 = Math.min(min_x1, x1[i]);
        }
        ans = Math.min(ans, max_x2 - min_x1);

        // 끝점이 가장 큰 선분 제거
        skip = 0;
        for(int i = 0; i < n; i++) {
            if(x2[skip] < x2[i]) skip = i;
        }

        max_x2 = 0;
        min_x1 = INT_MAX;
        for(int i = 0; i < n; i++) {
            if(i == skip) continue;
            max_x2 = Math.max(max_x2, x2[i]);
            min_x1 = Math.min(min_x1, x1[i]);
        }

        ans = Math.min(ans, max_x2 - min_x1);
        System.out.println(ans);
    }
}

특징

• 선분 전체를 포함하는 구간 길이가 줄어들 수 있는 경우는:
  • 시작점이 가장 작은 선분을 제외하거나
  • 끝점이 가장 큰 선분을 제외한 경우뿐이라는 점을 이용함
• 시간 복잡도: O(n)

---

비교 정리

항목	브루트 포스 방식	최적화 방식
시간 복잡도	O(n²)	O(n)
핵심 아이디어	모든 조합 비교	최소/최대 극단값 제거만 고려
코드 길이	간결	약간 복잡
실행 속도	느림 (n 증가 시 급격히 느려짐)	빠름

---