[백준]2170: 선 긋기 - JAVA

[백준]2170: 선 긋기

 

www.acmicpc.net/problem/2170

2170번: 선 긋기

풀이

선의 정보를 입력 받은 후 계산을 순차적으로 진행하기 위해 x좌표를 기준으로 오름차순 정렬을 한다. x좌표가 같으면 y 좌표를 기준으로 오름차순 정렬 한다.

 

이전 선의 정보를 min, max에 저장해 주었고 현재 선의 정보와 비교하면서 조건에 따라 길이를 계산해 주었다.

선의 길이를 계산할 때 다음과 같은 3가지 조건이 있다.(이때 모든 선은 x, y기준으로 오름차순 정렬되어 있다.)

 

(파란 선이 이전의 선이고 초록 선이 현재의 선 정보이다.)

1. 이전의 선에 현재 선이 겹친다. 

이럴 경우 계산하지 않고 무시하고 넘어가면 된다.

 

2. 이전의 선에 현재 선의 일부가 겹친다.

이럴 경우 현재 길이 정보에 더해야 하는 값은 7 - 5 = 2이다. 즉, 현재 선의 y좌표에서 이전 선의 y좌표를 뺀 값을 더해주면 된다.

 

3. 이전의 선과 현재 선이 겹치지 않는다.

이럴 경우에는 이전 선에 관계 없이 현재 선의 y좌표에서 x좌표를 뺀 값을 더해주면 된다.

 

이 과정을 코드로 구현하면 된다-!

(입력 받을때 scanner를 사용하면 시간 초과가 난다.)

코드

import java.io.*;
import java.util.*;
 
public class Main {    
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[][] pos = new int[n][2];
        int result=0;
        
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            int p1 = Integer.parseInt(line.split(" ")[0]);
            int p2 = Integer.parseInt(line.split(" ")[1]);
            pos[i][0] = p1;
            pos[i][1] = p2;
        }
        
        Arrays.sort(pos, new Comparator<int[]>() { //x좌표 오름차순 정렬. x좌표 같으면 y좌표 오름차순 정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0])  return o1[1] - o2[1];
                else  return o1[0] - o2[0];
            }
        }); 
        
        int min = pos[0][0];//이전 선의 x좌표
        int max = pos[0][1];//이전 선의 y좌표
        int len = max - min;
        for(int i = 1; i < n; i++) {
            if(min <= pos[i][0] && pos[i][1] <= max) { //현재 선이 이전 선에 포함된다면
                continue;
            } else if(pos[i][0] < max) { //현재 선의 시작점이 이전 선에 포함된다면
                len += pos[i][1] - max;
            } else { //현재 선과 이전 선이 겹치지 않는다면
                len += pos[i][1] - pos[i][0];
            }
            min = pos[i][0];
            max = pos[i][1];
        }
        System.out.println(len);
    }
}