[코드트리] 전부 겹치는 선분 2

h_jin·2025년 1월 9일

Java 완전탐색 코드트리

코테

목록 보기

6/33

문제링크

문제

x1, x2의 범위가 n개 주어지고
n개 중 1개를 제외했을 때,
n-1개의 선분이 겹치는 경우가 있는지

다른 풀이 (완전 탐색 X)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] lst = new int[101];

        for (int i = 0; i < n; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            for (int j = start; j <= end; j++)
                lst[j]++;
        }

        boolean res = false;
        for (int i = 0; i < 101; i++){
            if (lst[i] >= n - 1)
                res = true;
        }

        if (res)
            System.out.print("Yes");
        else
            System.out.print("No");

    }
}

전체를 한 Array에 표시하고, 겹치는 공간이 n - 1개 이상이면 선분 하나를 지웠을 때 조건에 만족하는 경우가 무조건 생김

풀이 (완전 탐색)

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 int n;
    public static int[] x1 = new int[MAX_N];
    public static int[] x2 = new int[MAX_N];
    public static boolean ans = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 입력
        n = sc.nextInt();
        for(int i = 0; i < n; i++) {
            x1[i] = sc.nextInt();
            x2[i] = sc.nextInt();
        }
        
        // 모든 선분을 한번씩 지어 보고, 모든 상황에 대해
        // 전부 겹치는 지점을 하나라도 만들 수 있는지 판단합니다.
        for(int skip = 0; skip < n; skip++) {
            int maxX1 = 0;
            int minX2 = INT_MAX;
            boolean possible = false;
            for(int i = 0; i < n; i++) {
                if(i == skip) continue;

                // 시작점 중 가장 뒤에 있는 좌표와 끝점 중 가장 앞에 있는 점의 좌표를 확인합니다.
                maxX1 = Math.max(maxX1, x1[i]);
                minX2 = Math.min(minX2, x2[i]);
            }

            // 만약 어느 한 선분이라도 시작점이 다른 선분의 끝점보다 뒤에 온다면
            // 선분이 전부 겹칠 수 없습니다.
            if(minX2 >= maxX1)
                possible = true;
            else
                possible = false;
            
            // 만약 한 가지 방법이라도 전부 겹치는 지점을 만들 수 있다면,
            // 하나의 선분을 적절하게 제거했을 때 전부 겹칠수 있다는 것이 되므로 할 수 있게 됩니다.
            if(possible)
                ans = true;
        }

        if(ans)
            System.out.print("Yes");
        else
            System.out.print("No");

    }
}