문제 - 2170 선긋기
문제
매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.
이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.
입력
첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.
출력
첫째 줄에 그은 선의 총 길이를 출력한다.
예제 입력 1
4
1 3
2 5
3 5
6 7
예제 출력 1
5
접근 방법
x에 대해 정렬한 뒤, 최대값을 저장하고 이를 비교하여 길이를 계산하는 방식
이 문제는 일직선 상에서 선을 그어 그 길이를 합을 구하는 문제이다.
그래서 나는 입력 값을 시작점 (x)으로 정렬하여, 계산해야 하는 범위를 줄였다.
2차원 배열의 정렬은 아래와 같이 람다식을 이용해 수행했다.
Arrays.sort(line, (o1, o2) -> {
if(o1[0]==o2[0])
return o1[1]-o2[1];
else
return o1[0]-o2[0];
});하지만 코드를 몇번을 수정해도, 3%에서 틀렸다라고 나왔다.
내가 놓친 부분은 과연 이전 값이 최대 값인가? 였다.
수정하기 전 내가 작성한 코드는 아래와 같다.
if(line[i][0]>line[i-1][1]) {
//이전 선에 포함이 되지 않는 경우
result += line[i][1]-line[i][0];
}
else if (line[i-1][1]>=line[i][1] && line[i][0]>=line[i-1][0]) {
continue;
}
else result += line[i][1]-line[i-1][1];이에 대한 반례로는
3
1,5
2,3
4,6
이 예제라고 할 때,
세번째 선을 그을 때 이전 y값인 3과 비교하면 첫번째 if 문으로 가게된다. 하지만 이미 선은 5까지 그어져 있어 정답이 틀린 것이었다.
최소값은 이미 정렬로 정해져있기 때문에 따로 계산 할 필요가 없었고, 최대 값만 비교 계산을 통해 갱신해주었다.
정답 코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int [][] line = new int [N][2];
for(int i=0;i<N;i++) {
String [] strs = br.readLine().split(" ");
line[i][0] = Integer.parseInt(strs[0]);
line[i][1] = Integer.parseInt(strs[1]);
}
Arrays.sort(line, (o1, o2) -> {
if(o1[0]==o2[0])
return o1[1]-o2[1];
else
return o1[0]-o2[0];
});
int result = line[0][1]-line[0][0];
int min = line[0][0];
int max = line[0][1];
for(int i=1;i<N;i++) {
if(line[i][0]>max) {
//이전 선에 포함이 되지 않는 경우
result += line[i][1]-line[i][0];
}
else if (max>=line[i][1]) {
continue;
}
else result += line[i][1]-max;
max = Math.max(max, line[i][1]);
}
System.out.println(result);
}
}
이 문제를 풀면서 배운 점은
경우의 수를 세분화 해서 생각하자.
