코드트리/ 최대로 겹치는 구간, 지점

최대로 겹치는 구간

30XP

공유하기

기본문제

정답률 61% · 제출 2,605회 · 예상 소요 시간 25분

21아쉬워요

1 StarEmpty내 리스트에 추가

---

1차원 직선 상에 n개의 선분이 놓여 있습니다. 가장 많이 겹치는 구간에서는, 몇 개의 선분이 겹치는지를 구하는 프로그램을 작성해보세요. 단, 겹치는 구간을 찾는 문제이므로 끝점에서 닿는 경우는 겹치는 것으로 생각하지 않습니다.

입력 형식

첫 번째 줄에는 n이 주어집니다.
두 번째 줄부터는 n개의 줄에 걸쳐 선분의 정보 (x1, x2)가 공백을 사이에 두고 주어집니다.

• 2 ≤ n ≤ 100
• -100 ≤ x1 < x2 ≤ 100

출력 형식

최대로 겹치는 구간에서, 몇 개의 선분이 겹치는 지를 출력합니다.

입출력 예제

예제1

입력:

3
1 5 
4 6
2 4

 

출력:

2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner (System.in);

        int n = sc.nextInt();
        int offset = 100;
        int [] arr = new int[201];

       for(int i =0; i<n; i++){
        int a = sc.nextInt();
        int b = sc.nextInt();

        for(int j=a+offset; j<b+offset; j++){

            arr[j]++;

        }

        }

        int max = 0;

        for(int i = 0; i<201; i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }

        System.out.print(max);


    }
}

 

 

최대로 겹치는 지점

10XP

공유하기

쉬움

정답률 73% · 제출 1,550회 · 예상 소요 시간 7분

16아쉬워요

1 StarEmpty내 리스트에 추가

---

1차원 직선 상에 n개의 선분이 놓여 있습니다. 가장 많이 겹치는 곳에서는, 몇 개의 선분이 겹치는지를 구하는 프로그램을 작성해보세요. 단, 끝점에서 닿는 경우에도 겹치는 것으로 봅니다.

입력 형식

첫 번째 줄에는 n이 주어집니다.
두 번째 줄부터는 n개의 줄에 걸쳐 선분의 정보 (x1, x2)가 공백을 사이에 두고 주어집니다.

• 2 ≤ n ≤ 100
• 1 ≤ x1 < x2 ≤ 100

출력 형식

최대로 겹치는 지점에서, 몇 개의 선분이 겹치는 지를 출력합니다.

입출력 예제

예제1

입력:

3
1 5 
4 6
2 4

 

출력:

3

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner (System.in);

        int n = sc.nextInt();
        int offset = 100;
        int [] arr = new int[201];

       for(int i =0; i<n; i++){
        int a = sc.nextInt();
        int b = sc.nextInt();

        for(int j=a+offset; j<=b+offset; j++){ //겹치는 "지점"이기 때문에 =이 붙음

            arr[j]++;

        }

        }

        int max = 0;

        for(int i = 0; i<201; i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }

        System.out.print(max);


    }
}