[BaekJoon] 2170 선 긋기

1.  문제 링크

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

2.  문제

요약

• 도화지에 선을 그을 때 자의 한 점에서 다른 한 점까지 긋게 되는데 이미 선이 있는 위치에 선을 겹쳐서 그릴 수도 있습니다.
• 여러 번 그은 곳과 한 번 그은 곳의 차이는 구별할 수 없습니다.
• 그려진 선들의 총 길이를 구하는 문제입니다.(선이 여러 번 그려진 곳은 한 번씩만 계산합니다.)
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 선을 그은 횟수 N이 주어지고 두 번째 줄부터 N개의 줄에는 -1,000,000,000보다 크거나 같고 1,000,000,000보다 작거나 같은 두 점의 위치 x, y들이 주어집니다.
• 출력: 첫 번째 줄에 그은 선의 총 길이를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public int getLineLength(ArrayList<Point> isLines) {
		Collections.sort(isLines);
		int start = isLines.get(0).start;
		int end = isLines.get(0).end;
		int length = end - start;
		for(int i = 1; i < isLines.size(); i++) {
			if(start <= isLines.get(i).start && isLines.get(i).end <= end) {
				continue;
			} else if(isLines.get(i).start < end) {
				length += -(end - isLines.get(i).start) + (isLines.get(i).end - isLines.get(i).start);
			} else {
				length += isLines.get(i).end - isLines.get(i).start;
			}
			start = isLines.get(i).start;
			end = isLines.get(i).end;
		}
		return length;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		ArrayList<Point> isLines = new ArrayList<>();
		for(int i = 0; i < num; i++) {
			String[] input = br.readLine().split(" ");
			int start = Integer.parseInt(input[0]);
			int end = Integer.parseInt(input[1]);
			isLines.add(new Point(Math.min(start, end), Math.max(start, end)));
		}
		br.close();
		Main m = new Main();
		bw.write(m.getLineLength(isLines) + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class Point implements Comparable<Point> {
		int start, end;
		public Point(int start, int end) {
			this.start = start;
			this.end = end;
		}
		@Override
		public int compareTo(Point e) {
			if(this.start != e.start) {				
				return this.start - e.start;
			} else {
				return this.end - e.end;
			}
		}
		
	}
}

4.  접근

• 주어진 (x, y)를 x를 기준으로 오름차순으로 정렬하고 만약 x가 같다면 y를 기준으로 오름차순으로 정렬합니다.
• 이전에 있던 선과 겹치지 않는 경우, 이전에 있던 선과 일부 겹치는 경우, 이전에 있던 선과 완전히 겹치는 경우 3가지가 발생할 수 있습니다.
• 이전에 있던 선과 완전히 겹치지 않는 경우는 길이에 해당 선의 길이를 추가해주지 않고 이전에 있던 선과 일부 겹치는 경우는 해당 선의 길이에서 겹치는 부분의 길이를 빼서 추가해주며 이전에 있던 선과 겹치지 않는 경우는 해당 선의 길이를 그대로 추가합니다.
• 해당 선이 이전에 있던 선과 완전히 겹치는 경우는 이전 선의 x와 y 사이에 해당 선의 x, y가 존재하는 경우입니다.
• 해당 선이 이전에 있던 선과 일부 겹치는 경우는 x를 기준으로 오름차순으로 정렬하였기 때문에 이전 선의 x보다 해당 선의 x가 작을 경우가 없으므로 해당 선의 x부터 이전 선의 y까지 겹치는 경우 밖에 없으므로 이전 선의 y보다 해당 선의 x가 작은 경우입니다.
• 위 두 경우가 아닌 경우가 이전에 있던 선과 겹치지 않는 경우가 됩니다.

1. (x, y)를 나타내는 Point 클래스를 생성하고 해당 클래스를 x를 기준으로 오름차순으로, x가 같다면 y를 기준으로 오름차순으로 정렬하려고 하기 때문에 해당 부분을 Comparable을 이용해 구현해줍니다.
2. 주어진 (x, y)를 더 작은 값을 x, 더 큰 값을 y로 하여 Point를 생성해 ArrayList isLines에 저장하고 Point들을 위 기준으로 정렬해줍니다.
3. 이전 선의 시작점을 나타내는 start 변수와 이전 선의 끝점을 나타내는 end 변수를 생성하고 첫 번째 선의 시작점과 끝점으로 각각 초기화시켜줍니다.
4. 선의 길이의 합을 나타내는 변수 length를 생성하고 첫 번째 선의 길이인 (end - start) 값으로 초기화시켜줍니다.
5. 두 번째 선부터 마지막 선까지 반복문을 돌면서 선의 총 길이를 구합니다.
   1. 만약 start보다 현재 선의 x가 크거나 같고 현재 선의 y가 end보다 작거나 같다면 선이 완전히 겹치는 경우가 되므로 다음 선으로 넘어갑니다.
   2. 현재 선의 x가 end보다 작다면 선의 일부가 겹치는 경우이므로 현재 선의 길이에서 (end - 현재 선의 x)값을 빼준 후에 해당 값을 length에 추가시켜줍니다.
   3. 위 두 경우 모두 아니라면 선이 겹치지 않는 경우이므로 해당 선의 길이를 length에 추가시켜줍니다.
   4. start는 현재 선의 x로, end는 현재 선의 y로 변경시켜줍니다.
6. 5번의 반복문이 끝났을 때의 length가 선의 총 길이가 되므로 해당 값을 출력합니다.