JAVA 백준 2170 선 긋기 (스와핑)

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

 

---

문제

1. 첫째 줄에 정수 N (1 <= N <= 1000000)이 주어진다.
2. 둘째 줄부터 N개의 줄에 선을 그을 떄 선택한 두 점의 위치 x, y  (-1000000000 <= x, y <= 1000000000)가 주어진다.
3. 한 번 선을 그은 곳과 여러 번 선을 그은 곳을 구분할 수 없을 때, 그려진 모든 선의 총 길이를 출력하라.

---

 

최종 코드 (보기 쉬운 버전)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static class Line {
        int start;
        int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

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

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

        Line[] lines = new Line[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            lines[i] = new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(lines, Comparator.comparingInt(o -> o.start));

        ArrayList<Line> list = new ArrayList<>();

        list.add(lines[0]);

        for (int i = 1; i < N; i++) {
            if (lines[i].start <= list.get(list.size() - 1).end) {
                if (list.get(list.size() - 1).end < lines[i].end) {
                    list.get(list.size() - 1).end = lines[i].end;
                }
            } else {
                list.add(lines[i]);
            }
        }

        int result = 0;

        for (int i = 0; i < list.size(); i++) {
            result += list.get(i).end - list.get(i).start;
        }

        System.out.println(result);
    }
}

 

모든 선들을 시작 점인 x(start)를 기준으로 오름차순 정렬하여

1. list에 있는 마지막 인덱스의 Line 객체의 y(end)보다 비교되는 lines에 있는 객체의 x(start)가 더 작을 때

2. list에 있는 마지막 인덱스의 Line 객체의 y(end)보다 비교되는 lines에 있는 객체의 y(end)가 더 클 때

이 두 가지 조건을 만족할 때 두 선은 겹치는 부분과 겹치지 않는 부분을 모두 갖는 선이 된다.

 

선의 정보가 담긴 배열을 x(start)를 기준으로 오름차순 정렬하였기 때문에 1번을 만족할 때 이미 겹치는 부분이 있게 되므로

1번과 2번을 따로 나눠주어야 list에 겹치는 선이 추가되지 않게 할 수 있다.

 

이 두 조건을 모두 만족하지 않으면 겹치는 부분이 하나도 없는 새로운 선이므로 새롭게 추가를 해주면 된다.

 

마지막으로 list에 있는 선들의 총 길이를 구하면 답이 된다.

 

 

조금 더 짧은 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static class Line {
        int start;
        int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

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

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

        Line[] lines = new Line[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            lines[i] = new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(lines, Comparator.comparingInt(o -> o.start));

        Line temp = lines[0];
        int result = 0;

        for (int i = 1; i < N; i++) {
            if (lines[i].start <= temp.end) {
                if (temp.end < lines[i].end) {
                    temp.end = lines[i].end;
                }
            } else {
                result += temp.end - temp.start;
                temp = lines[i];
            }
        }
        
        result += temp.end - temp.start;

        System.out.println(result);
    }
}

 

새로운 선을 list에 추가하지 않고, 겹치지 않는 선이 생겼을 때 기존의 선을 최종 정답이 들어갈 변수에 더하고 새로운 선을 변수에 담아 반복문을 재개한다.

 

마지막에 더해지지 못한 선까지 더해주면 총 선의 길이가 나오게 된다.