[BOJ 2170] 선 긋기 (Java)

문제

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

2170번: 선 긋기

 

풀이

스위핑 기법으로 x좌표 오름차순(같을 경우 y좌표 오름차순 정렬) 후, 라인을 하나씩 체크하면서 길이를 더해나간다. 

4
1 3
2 5
3 5
6 7

예제 데이터를 아래와 같이 정렬 한다. 

1--3

   2---5

     3--5

            6-7

 

prev는 현재까지 진행된 라인의 y값 중 가장 큰 값을 저장

 

1--3

길이 2

prev = 3

 

2---5: 

길이: 2

prev가 3이므로 5-3 = 2

2-3구간은 이전 라인과 중복되기 때문

prev = 5

 

3--5:

길이: 0

prev가 5이므로 현재까지의 라인이 해당 라인을 모두 포함한다. 

아무것도 더하지 않는다. 

 

6-7:

길이: 1

prev가 라인의 시작보다 작으므로 7-6 = 1

prev = 7

 

총 길이: 5

 

소스코드

package sweeping;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ2170 {

    public static class Line implements Comparable<Line>{
        int x;
        int y;

        public Line(int x, int y){
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Line l){
            int rs = this.x - l.x;
            if(rs == 0) rs = this.y - l.y;
            return rs;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        ArrayList<Line> list = new ArrayList<Line>();
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            list.add(new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        Collections.sort(list);
        int answer = list.get(0).y-list.get(0).x;
        int prev = list.get(0).y;
        for(Line line : list){
            if(prev >= line.y){
                // 이전 라인이 현재 라인을 포함
                // nothing
            } else if(prev < line.y && prev > line.x){
                // 이전 라인의 끝이 현재 라인 내에 포함되어 있음
                answer += line.y-prev;
                prev = line.y;
            } else {
                // 이전 라인의 끝이 현재 라인 전에 끝이 나있음.
                answer += line.y-line.x;
                prev = line.y;
            }
        }
        System.out.println(answer);
    }
}