[백준] 2170번 : 선 긋기

문제

 

 

접근 방식

1 3
2 5
3 5
6 7

 

위와 같이 일직선 상의 선분의 시작점과 끝점이 주어졌을 때

시작점이 가장 작은 순으로 정렬하고 각 선분을 그어보면

세 가지 경우로 선분을 그을 수 있는데

1 2 3 4 5 6 7
1   3
  2     5
    3   5
          6 7

 

위와 같이 처음 1-3 선분이 있을 때

다음에 오는 2-5 선분은 이전 1-3선분에 겹치면서 길이가 조금 더 긴 경우

3-5 선분은 이전 선분 자체에 모두 겹치는 경우

6-7 선분은 겹치지 않는 새로운 선분인 경우다.

 

완전히 새로운 경우에는 끝점 - 시작점으로 선분의 길이를 구할 수 있고

겹치는 경우에는 겹치지 않는 경우만 계산하면 되기 때문에

현재 선분의 끝점에서 이전 선분의 끝점을 빼주면 되고

완전히 겹치는 경우에는 계산할 필요가 없다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int[][] xy = new int[n][2];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			xy[i][0] = Integer.parseInt(st.nextToken());
			xy[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(xy, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);

		int s = xy[0][0];
		int e = xy[0][1];
		int len = e - s;

		for (int i = 1; i < n; i++) {
			int x = xy[i][0];
			int y = xy[i][1];

			if (y <= e) continue;

			if (x <= e) {
				len += (y - e);
			} else {
				len += y - x;
			}

			e = y;
		}

		System.out.println(len);
	}
}