[PS] BOJ2170 선긋기 ( LineSweeping ) with JAVA

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

2170번: 선 긋기

 

◎ 문제풀이

 

선을 입력 받고 선을 시작점을 기준으로 내림차순 정렬한 뒤 하나씩 가져와 비교해본다. 

그럼 경우는 3가지가 있다. 

 

파란선 : 기존선

연두선 : 새로운 선

 

1) 완전히 겹치는 경우

 

 

완전히 겹치는 경우는 무시하고 넘어간다. 

 

2) 부분이 겹치는 경우 

 

 

 

 

부분이 겹치면 시작점은 그대로이고 종료점이 새로운 선의 종료점까지 늘어난다. 

 

3) 안 겹치는 경우

 

 

시작점을 기준으로 정렬하여 하나씩 선을 가져오는 것이기에, 겹치지 않으면 기존의 선은 더이상 어떤 선과도 겹치지 않는다. 새로운 연두색 선이 이제 기준이 된다. 

 

 

◎코드

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

//BOJ2170 선긋기
public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int[][] lines;

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    private static void solution() {
        int start = lines[0][0];
        int end = lines[0][1];
        int ans = 0;

        for (int[] line : lines) {
            int s = line[0];
            int e = line[1];

            if( s <= end && e <= end ) continue; // 선이 완전히 겹치는 경우
            else if ( s <= end && end < e) { // 선이 부분 겹치는 경우
                end = e;
            }
            else if ( end < s){ // 선이 안 겹치는 경우
                ans += end - start; 
                start = s;
                end = e;
            }
        }
        ans += end - start;
        System.out.println(ans);
    }


    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        lines = new int[n][2];
        for(int i =0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            lines[i][0] = start;
            lines[i][1] = end;
        }
        Arrays.sort(lines,(line1, line2)->Integer.compare(line1[0],line2[0])); // 시작점으로 내림차순 정렬
    }
}