[백준] 2170번 선 긋기

1. 문제

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

여러 개의 선분이 주어질 때 겹치는 부분을 제외한 전체 선의 길이를 구하는 문제이다.

4
1 3
2 5
3 5
6 7

주어진 입력이 위와 같을 때
1. (1, 3)과 (2, 5)가 겹치므로 합쳐져 (1, 5)가 된다.
2. (1, 5)와 (3, 5)가 겹치므로 (1, 5)를 유지한다.
3. (1, 5)와 (6, 7)은 겹치지 않으므로 최종 선분은 (1, 5)와 (6, 7)이 되며, 전체 선분의 길이는 4 + 1 = 5이다.

2. 풀이

class Line {
    int s; // 시작점
    int e; // 끝점
    
    Line(int s, int e) {
        this.s = s;
        this.e = e;
    }
}

각 선분의 시작점(s)과 끝점(e)을 저장하는 클래스이다.

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

list: 입력받은 모든 선분들을 저장하는 리스트
lines: 겹치지 않도록 정리된 선분들을 저장하는 리스트

Collections.sort(list, (a, b) -> (a.s - b.s));

겹치는 선분들을 편리하게 처리하기 위해 오름차순으로 정렬한다.

lines.add(new Line(list.get(0).s, list.get(0).e)); 
int j = 0;
for (int i=1; i<n; i++) {
    Line l = lines.get(j);
    Line l2 = list.get(i);

    if (l2.s >= l.s && l2.s <= l.e && l2.e > l.e) {
        l.e = l2.e;
    } else if (l2.s > l.e) {
        lines.add(new Line(l2.s, l2.e)); 
        j++;
    }
}

첫 번째 선분을 lines 리스트에 추가하고 나머지 선분들을 순회하면서 겹치는 부분을 처리한다. 현재 선분(l2)이 이전 선분(l)과 겹친다면 l.e를 l2.e로 업데이트하여 선분을 확장한다. 겹치지 않는 새로운 선분이 나오면 lines 리스트에 추가하고 새로운 선분을 기준으로 또 다시 겹치는 부분을 처리한다.

int len = 0;
for (int i=0; i<lines.size(); i++) {
    len += (lines.get(i).e - lines.get(i).s);
}
System.out.println(len);

최종적으로 정리된 lines 리스트를 순회하며 겹치지 않는 선분의 총 길이를 합산한다.

3. 소스 코드

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

class Line {
    int s;
    int e;
    
    Line(int s, int e) {
        this.s = s;
        this.e = e;
    }
}
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Line> list = new ArrayList<>();
        List<Line> lines = new ArrayList<>();
        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list.add(new Line(x, y));
        }
        Collections.sort(list, (a, b) -> (a.s - b.s));
        lines.add(new Line(list.get(0).s, list.get(0).e));
        int j = 0;
        for (int i=1; i<n; i++) {
            Line l = lines.get(j);
            Line l2 = list.get(i);
            if (l2.s >= l.s && l2.s <= l.e && l2.e > l.e) {
                l.e = l2.e;
            } else if (l2.s > l.e) {
                lines.add(new Line(l2.s, l2.e));
                j++;
            }
        }
        int len = 0;
        for (int i=0; i<lines.size(); i++) {
            len += (lines.get(i).e - lines.get(i).s);
        }
        System.out.println(len);
    }
}