백준 2170 (선 긋기) - java

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

2170번: 선 긋기

 

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

 

유형 : 정렬 + 스위핑

 

접근 방식

• 정렬의 기준이 중요하다.
  • 시작점이 작은 순으로 -> 길이가 같은 순으로
• 두가지
  • 다음 직선이 기존 직선의 연장선인지 체크
  • 아예 떨어져 있는 직선인지
    • 떨어져 있다면 기존 직선의 길이를 결과에 더해준다.

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n = 0;


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

        n = Integer.parseInt(st.nextToken());
        Node[] arr = new Node[n];

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

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            arr[i-1] = new Node(s,e);
        }

        Arrays.sort(arr,(x,y) -> {

            if(x.s == y.s)
                return y.e - x.e;

            return x.s - y.s;
        });

        int s = arr[0].s;
        int e = arr[0].e;

        int result = 0;

        for(int i=1;i<n;i++){
            Node cur = arr[i];

            if(cur.s <= e && cur.e >= e){
                e = Math.max(e,cur.e);
            }

            else if(cur.s > e){
                result += (e - s);

                s = cur.s;
                e = cur.e;
            }
        }

        result += (e - s);

        System.out.println(result);
        br.close();
    }
}
class Node{
    int s;
    int e;

    Node(int s,int e){
        this.s = s;
        this.e = e;
    }
}