문제풀이/백준
[백준]2170: 선 긋기 - JAVA
빈둥벤둥
2021. 2. 18. 16:18
[백준]2170: 선 긋기
2170번: 선 긋기
첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.
www.acmicpc.net
풀이
선의 정보를 입력 받은 후 계산을 순차적으로 진행하기 위해 x좌표를 기준으로 오름차순 정렬을 한다. x좌표가 같으면 y 좌표를 기준으로 오름차순 정렬 한다.
이전 선의 정보를 min, max에 저장해 주었고 현재 선의 정보와 비교하면서 조건에 따라 길이를 계산해 주었다.
선의 길이를 계산할 때 다음과 같은 3가지 조건이 있다.(이때 모든 선은 x, y기준으로 오름차순 정렬되어 있다.)
(파란 선이 이전의 선이고 초록 선이 현재의 선 정보이다.)
1. 이전의 선에 현재 선이 겹친다.
이럴 경우 계산하지 않고 무시하고 넘어가면 된다.
2. 이전의 선에 현재 선의 일부가 겹친다.
이럴 경우 현재 길이 정보에 더해야 하는 값은 7 - 5 = 2이다. 즉, 현재 선의 y좌표에서 이전 선의 y좌표를 뺀 값을 더해주면 된다.
3. 이전의 선과 현재 선이 겹치지 않는다.
이럴 경우에는 이전 선에 관계 없이 현재 선의 y좌표에서 x좌표를 뺀 값을 더해주면 된다.
이 과정을 코드로 구현하면 된다-!
(입력 받을때 scanner를 사용하면 시간 초과가 난다.)
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
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);
}
}
|
cs |