백준 2170 선긋기 - 그리디

문제 링크

풀이 흐름 : 그리디

범위가 작았더라면 배열을 선언해서 boolean으로 체크해볼 수 있겠지만, 범위가 최대 20억이기 때문에 시간초과가 난다.

그보다 효율적으로 접근해야 한다. N 는 100만이기 때문에 N을 하나씩 처리해나가려 한다.

N를 정렬해주고 가장 앞의 선 부터 처리하도록 하자.

놓친점 1

범위가 -10억부터 포함인데, 시작 line을 0으로 두고 시작해서 틀렸다.

범위를 잘 보고 초깃값 세팅에 더 주의하도록 하자.

놓친점 2

이렇게 앞에서 부터 차례대로 처리해나가는 것을 라인 스위핑문제라고 한다.

이렇게 현재위치를 앞으로 옮기면서 처리해나갈때 start, end가 모두 현재위치보다 뒤에있는 경우를 생각해줘야 한다.

이번 문제에서는 T의 위치를 앞전 Node의 end지점으로 설정해두었다. 하지만 정렬을 start 기준으로 오름차순이었기 때문에 end 지점이 뒤로갈 위험이 있었다. 주의하도록 하자

최종 코드

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


class Solution {

    static int[] parent ;

    public int find(int x){
        if(parent[x]==x){
            return x;
        }

        return find(parent[x]);
    }

    public void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
        {
            parent[y]=x;
        }
        else{
            parent[x]=y;
        }
    }

    public int solution(int n, int[][] computers) {

        int answer = 0;
        parent = new int[n+1];


        // 1인덱스
        for(int i=1;i<=n;i++){
            parent[i]=i;
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){

                if(computers[i][j]==1){
                    int a = i+1;
                    int b = j+1;

                    //union(a,b);
                }
            }

        }


        parent[100]=1;
        int[] root = new int[n+1];

        for(int i=1;i<=n;i++){
            root[find(i)]=1;

            System.out.print(String.valueOf(parent[i])+" ");
        }

        int ans = 0;
        for(int i=1;i<=n;i++){
            if(root[i]==1){
                ans++;
            }
        }



        return ans;
    }
}
public class Main {

    static class Node {
        int s;
        int e;

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

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        ArrayList<Node> arr = new ArrayList<Node>();
        for(int i=0;i<n;i++){
            String[] inp = br.readLine().split(" ");

            int x = Integer.parseInt(inp[0]);
            int y = Integer.parseInt(inp[1]);
            arr.add(new Node(x,y));
        }

        Collections.sort(arr, new Comparator<Node>(){
            @Override
            public int compare(Node a, Node b){
                if( a.s == b.s){
                    return a.e - b.e;
                }

                return a.s - b.s;
            }
        });

        long ans = 0;
        int line = -1000000000;
        for(Node cur : arr){

            if(cur.e >= line) {

                ans += (cur.e - Math.max(line, cur.s));
//            System.out.println(cur.e - Math.max(line,cur.s));
                line = cur.e;
            }
        }

        System.out.println(ans);
    }
}