[정렬] 백준 2170번 선 긋기 Java(자바)

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

2170번: 선 긋기

 

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

코드1 (Scanner)

시간초과

import java.util.*;

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

        int N = sc.nextInt();
        int[][] arr = new int[N][2];


        for(int i=0; i<N; i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] == o2[0])
                return o1[1] - o2[1];
            else
                return o1[0] - o2[0];
        });  //2차원 배열 정렬

        int x = arr[0][0];
        int y = arr[0][1];
        int len = y-x;
        for(int i = 0; i < N; i++){
            if(x <= arr[i][0] && arr[i][1] <= y) { //포함된 경우
                continue;
            } else if(arr[i][0] < y) { //일부만 포함된 경우
                len += arr[i][1] - y;
            } else { //겹치는 부분이 없는 경우
                len += arr[i][1] - arr[i][0];
            }
            x = arr[i][0];
            y = arr[i][1];
        }
        System.out.println(len);
        sc.close();
    }
}

 

코드2(Buffer)

import java.util.*;
import java.io.*;

public class No2170 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];

        for(int i=0; i<N; i++){
            String line = br.readLine();
            arr[i][0] = Integer.parseInt(line.split(" ")[0]);
            arr[i][1] = Integer.parseInt(line.split(" ")[1]);
        }

        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] == o2[0])
                return o1[1] - o2[1];
            else
                return o1[0] - o2[0];
        });  //2차원 배열 정렬

        int x = arr[0][0];
        int y = arr[0][1];
        int len = y-x;
        for(int i = 0; i < N; i++){
            if(x <= arr[i][0] && arr[i][1] <= y) { //포함된 경우
                continue;
            } else if(arr[i][0] < y) { //일부만 포함된 경우
                len += arr[i][1] - y;
            } else { //겹치는 부분이 없는 경우
                len += arr[i][1] - arr[i][0];
            }
            x = arr[i][0];
            y = arr[i][1];
        }
        System.out.println(len);
    }
}

풀이

입력 받은 x,y 값을 정렬한후 아래에 있는 조건들로 나누어 처리한다.

1. 기존 선에 겹치는 경우에는 그냥 넘어간다.

 

2. 일부만 포함된 경우 이전 선의 y값에서 현재 선의 y값을 뺀값을 길이에 더한다.

 

3. 겹치는 부분이 없는 경우 현재 선의 y값에서 x값을 뺀값을 길이에 더한다.

 

주의사항

Scanner를 사용하는데 시간초과가 난다면 Buffer을 이용하여 문제를 풀어야 한다.

그동안 scanner가 더 손에 익어서 계속 사용해왔는데 scanner는 느리다는 단점이 있어서

시간 제한이 짧은 문제들은 계속 시간초과가 난다.

 

 

2차원 배열 정렬

2차원 배열에 대한 설명은 아래에 정리되어 있다.

https://seaotter.tistory.com/4

[그리디] 백준 11000번 강의실 배정