[백준BOJ] 2170번 선 긋기.java

 

백준 저지에서 선 긋기를 자바를 통해 풀어 보았다. 

 

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

2170번: 선 긋기

2170번 선 긋기.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

2170번 선 긋기

문제

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

설명

자를 대고 선을 긋는다. 이때의 양 끝 좌표를 l,r라고 하자. 여러개의 선을 긋는데 중복되는 선이 있더라도 하나의 선으로 취급한다. 즉 두개의 선이 중복되는 부분이 있다면 하나의 선이 된다. 

 

일단 모든 선을 입력받아 저장한다. 선과 선이 중복되는 경우는 여러가지가 있는데 여러개의 선이 겹치다보면 다양한 경우가 나오기 때문에 이를 모두 처리하기는 어렵다. 그렇기 때문에 나올 수 있는 경우의 수를 정렬을 통해 줄인다.

 

모든 선에 대해서 각 선의 l을 기준으로 정렬하면 경우의 수가 2가지 뿐이다. 이미 존재하는 선과 뒤에 오는 선이 중복되는 경우와 중복되지 않는 경우이다. 

 

만약 중복된다면 두 선을 합친다. 현재 선의 r과 뒤에 오는 선의 r 중 더 큰 값으로 갱신한다.

 

만약 중복되지 않는다면 기존에 있던 선은 그대로 둔 채 새로운 선을 만든다.

 

위 과정을 반복한다.

코드

//2170번 선 긋기.java
package week4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

class paper{
	public int x;
	public int y;
	paper(int x, int y){
		this.x=x;
		this.y=y;
	}
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}
	
}
public class 선_긋기_2170 {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static int N;
    static List<paper> p = new ArrayList<paper>();
    static int answer=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			p.add(new paper(x,y));
		}
		
		p.sort(new Comparator<paper>() {
			@Override
			public int compare(paper o1, paper o2) {
				return Integer.compare(o1.getX(), o2.getX());
			}
		});
		
		int x = p.get(0).x;
		int y = p.get(0).y;
		
		for(int i=1;i<p.size();i++) {
			if(p.get(i).x <= y) {
				y = Math.max(y, p.get(i).y);
			}
			else {
				answer += y-x;
				x = p.get(i).x;
				y = p.get(i).y;
			}
		}
		answer += y-x;
		
		System.out.println(answer);
	}
}