[BOJ/JAVA] 백준 2170 : 선 긋기 (자바)

문제 정보

  문제명   - 선 긋기
  난이도   - 골드 V
문제 번호 - 2170번

---

문제 링크

BOJ_G5_2170_선_긋기

2170번: 선 긋기

---

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.
이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

---

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

---

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
4 1 3 2 5 3 5 6 7	5

---

알고리즘 분류

● 정렬
● 스위핑

---

소스코드

package Lv3_Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 정렬, 스위핑
 * https://www.acmicpc.net/problem/2170
 */
class Line implements Comparable<Line>{
	int start;
	int end;
	public Line(int start, int end) {
		this.start = start;
		this.end = end;
	}
	@Override
	public int compareTo(Line o) {
		return this.start - o.start;
	}
}
public class BOJ_G5_2170_선_긋기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int N = Integer.parseInt(br.readLine());
		ArrayList<Line> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			list.add(new Line(start, end));
		}
		Collections.sort(list);
		int start = list.get(0).start;
		int end = list.get(0).end;
		int result = end-start;
		for (Line line : list) {
			// 중복되는 선은 continue
			if(line.end <= end) continue;
			// 라인이 이어진다면 추가되는 부분만 더함.
			if(line.start < end)
				result += line.end - end;
			// 라인이 끊긴다면 새로 그어준다.
			else
				result += line.end - line.start;
			// 새로 그은 선의 정보를 넣어준다.
			start = line.start;
			end = line.end;
		}
		System.out.println(result);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---